题解：AT_ddcc2017_final_e 足のばし

wrkwrkwrk · 2025-09-24 11:14:18 · 题解

~~注意到/可以猜到/感觉上全部在叶子上操作。~~

稍微证明一下：

操作顺序不重要。假设有个操作不在叶子所在边上，则其边权 \geq 2。将其减去 1 后：

直径减小，那么加到哪里都不会比原来更差。
直径不变。那么由于所有直径相交，且不存在直径经过这个边（因为经过这个边的所有路径都减去了 1），则必然存在一头和直径无关。由于不是叶子所在边，必然那一头存在叶子所在边和直径无关。加到那里就行。

在叶子上加相当于在叶子上挂点求直径。

贪心考虑先使得直径不变，这里先求出一条直径，对中间的叶子全部填充即可。

然后考虑所有直径相交导致的结果是存在所谓中心点。直径变化 1 的同时中心点必然变化。注意中心点可能在点也可能在边上。

考虑中心点偏移导致的结果：向一个方向偏移可以使得这边的所有叶子都允许 +1 行动。

考虑中心点偏移的过程：每次尽量向叶子多的方向偏移。

考虑中心点偏移的全过程：先向一个方向走，然后周期为 2 的来回走。

“一个方向走”的步数不会超过 2n-1，走 2n+1 步后看下最后两个就行。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
#define int long long
vector<int>g[1000006];
int dep[1000006];
int f[1000006];
void dfs(int now,int fa){
    f[now]=fa;
    dep[now]=dep[fa]+1;
    for(auto x:g[now])if(x!=fa){
        dfs(x,now);
    }
}
int base;
bool vis[1000006];
int rk[1000006];
int dc[1000006];
int sic[1000006];
int hprc[1000006];
int len,fr;
void dfs2(int now,int fa){
    dc[now]=dc[fa]+1;
    sic[now]=0;
    for(auto x:g[now])if(x!=fa&&!rk[x]){
        dfs2(x,now);
        sic[now]+=sic[x];
        hprc[now]=max(hprc[now],sic[x]);
    }
    if(g[now].size()==1){
        sic[now]=1;
        int qc=len-max(rk[fr]-1,len-rk[fr]);
        assert(dc[now]<=qc);
        base+=qc-dc[now];
    }
}
int de[1000006],sit[1000006],ss[1000006],sp[1000006];
int tot;
void dfs3(int now,int fa){
    de[now]=de[fa]+1;
    sit[now]=0;
    for(auto x:g[now])if(x!=fa){
        dfs3(x,now);
        sit[now]+=sit[x];
    }
    if(g[now].size()==1)sit[now]++;
    ss[now]=-1;
    for(auto x:g[now]){
        int dic;
        if(x!=fa)dic=sit[x];
        else dic=tot-sit[now];
        if(dic>ss[now]){
            ss[now]=dic;
            sp[now]=x;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    int x=max_element(dep+1,dep+1+n)-dep;
    dfs(x,0);
    int y=max_element(dep+1,dep+1+n)-dep;
    len=dep[y];
    vector<int>buf;
    int nc=y;
    int cc=1;
    while(nc){
        buf.push_back(nc);
        rk[nc]=cc++;
        nc=f[nc];
    }
    tot=0;
    for(int i=1;i<=n;i++)if(g[i].size()==1)tot++;
    for(auto f:buf){
        fr=f;
        dfs2(fr,0);
    }
    dfs3(x,0);
    bool typ;
    int l1,l2,ll;
    if(buf.size()&1){
        typ=0;
        ll=buf[buf.size()/2];
    }else{
        typ=1;
        l1=buf[buf.size()/2-1];
        l2=buf[buf.size()/2];
    }
    vector<int>frs={base};
    auto dnext=[&](){
        if(typ==0){
            frs.push_back(ss[ll]);
            l2=sp[ll];
            l1=ll;
            typ=1;
        }else{
            int a,b;
            if(de[l1]>de[l2]){
                a=sit[l1];b=tot-a;
            }else{
                b=sit[l2];a=tot-b;
            }
            if(a>b){
                frs.push_back(a);
                ll=l1;
            }else{
                frs.push_back(b);
                ll=l2;
            }
            typ=0;
        }
    };
    for(int i=0;i<=2*n;i++){
        dnext();
    }
    int pp,qq;
    qq=frs.back();frs.pop_back();
    pp=frs.back();frs.pop_back();
    for(int i=1;i<frs.size();i++){
        frs[i]+=frs[i-1];
    }
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        if(x<=frs.back()){
            auto c=lower_bound(frs.begin(),frs.end(),x)-frs.begin();
            cout<<len-1+c<<'\n';
        }else{
            int base=len-1+frs.size()-1;
            x-=frs.back();
            int tot=x/(pp+qq),wie=x%(pp+qq);
            base+=tot*2;
            if(wie>=1)base++;
            if(wie>pp)base++;
            cout<<base<<'\n';
        }
    }

    return 0;
}
}
bool en;
signed main(){
       #ifdef LOCAL_WRK
    //    cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
       #endif
          return _wrk::main();
}

AC 记录。

一个假做法但是能过 AT 数据。

假做法的 hack：