题解：CF1712F Triameter

· · 题解

分析

加入了叶子之间长度为 x 的边，直径上最多有一条新加入的边。

这使得树的直径变成 \max_{u,v} \min(dist(u,v),f_u+f_v+x)。

其中 f_u 表示 u 与最近叶子节点的距离，dist(u,v) 表示树上两点之间的距离，均容易处理，lca 的使用预处理 O(log_2 n)，查询 O(1) 的算法，例如 dfn 序求 lca。

那么就会衍生出两种思考方式：

考虑固定 u，考虑 v

由于 lca(u,v) 不固定，那么 dist(u,v) 不好入手，考虑从 f_u+f_v+x 入手。

二分答案 D，则有要求 f_v\ge K=D-f_u-x，找到所有满足这个要求的点组成的点集 S，下面要处理的就是 \max_{v\in S} dist(u,v)，检查这个东西是不是大于 D。

对于 \max_{v\in S} dist(u,v) 是容易处理的，只需要找出在树上点集 S 的直径，设直径端点为 l,r，则 \max_{v\in S} dist(u,v)=\max(dist(u,l),dist(u,r))。

那么如何找到 l,r，按 f_v 值从大到小插入点集 S，每次插入考虑新的直径端点 (l,r),(l,v),(v,r)，就可以单次 O(1) 更新直径端点。

这样就可以预处理出对于所有 K 对应的点集 S 的直径端点 L_K,R_K。

时间复杂度 O(n\log n+n\log nq)，实则足以通过。

实则 D 不用二分，先令 D=0，在枚举 u 的过程中检查 D+1 是否合法，合法即更新 D\larr D+1，实现具体见代码，时间复杂度 O(n\log n +nq)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int p[N],n,st[N][25],dfn[N],fa[N],f[N],dep[N],cnt;
vector<int>z[N];
int get(int x,int y){
    return dfn[x]<dfn[y]?x:y;
}
void dfs(int x){
    dep[x]=dep[fa[x]]+1;
    dfn[x]=++cnt;
    st[cnt][0]=fa[x];
    for(int i:z[x]){
        if(i==fa[x])continue;
        dfs(i);
    }
}
void init(){
    for(int i=1;i<=__lg(n);i++)for(int j=1;j+(1<<i)-1<=n;j++)st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
} 
int lca(int x,int y){
    if(x==y)return x;
    int a=dfn[x],b=dfn[y];
    if(a>b)swap(a,b);
    int k=__lg(b-a);
    a++;
    return get(st[a][k],st[b-(1<<k)+1][k]);
}
int dist(int x,int y){
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int l,r,nowd,L[N],R[N];
vector<int>mo[N];
int main(){
//  freopen("diameter.in","r",stdin); 
//  freopen("diameter.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        z[i].push_back(fa[i]),z[fa[i]].push_back(i);
    }
    queue<int>ye;
    for(int i=1;i<=n;i++){
        if(z[i].size()==1)p[i]=-1,ye.push(i);
    }
    while(!ye.empty()){
        int a=ye.front();
        ye.pop();
        for(int i:z[a]){
            if(!f[i]&&!p[i]){
                f[i]=f[a]+1;
                ye.push(i);
            }
        }
    }
    for(int i=1;i<=n;i++)mo[f[i]].push_back(i);
    dfs(1);
    init();
    for(int k=n;k>=0;k--){
        for(int i:mo[k]){
            if(!l&&!r)l=r=i,nowd=0;
            else {
                int a=dist(l,i),b=dist(r,i);
                if(max(a,b)>nowd){
                    if(a>b)r=i,nowd=a;
                    else l=i,nowd=b;
                }
            } 
        }
        L[k]=l,R[k]=r; 
    } 
    int q;
    cin>>q;
    while(q--){
        int a;
        cin>>a;
        int ans=0;
        for(int i=1;i<=n;i++){
            while(ans<n){
                int D=ans+1,k=max(D-a-f[i],0);
                if(max(dist(L[k],i),dist(R[k],i))<D||!L[k])break;
                ans=D; 
            }
        }
        cout<<ans<<" ";
    }
    return 0;
}

考虑固定 lca，考虑 u,v

固定了 lca，那么 dist(u,v)=dep_u+dep_v-2dep_{lca}，考虑从此处入手。

根据上面的方法处理 D。

令 g_{u,k} 表示在 u 的子树内，与 u 的距离 \ge k 的节点中 f_v 的最大值。

转移容易：

g_{u,i}\larr g_{v,i-1}

检查 D 是否可以拓展到 D+1 是简单的，分两种情况：

问题在于当前 g 的处理是 O(n^2) 的，但是这个转移方程非常优美，相当于 u 的所有孩子的 g_v 值右移一位贡献给 g_u 的相应位置，树链剖分，u 继承长儿子的 g 值，共用一段内存，空间被压缩到 O(n)，真正要处理的是所有非长儿子，这个时间是 O(n) 量级。

时间复杂度 O(nq)，实现不太优美常数有点大。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,p[N],fa[N],f[N],dep[N],son[N],*g[N],dp[N],*s=dp,h[N];
vector<int>z[N];
void dfs(int x){
    h[x]=0;
    dep[x]=dep[fa[x]]+1;
    for(int i:z[x]){
        if(i==fa[x])continue;
        dfs(i);
        h[x]=max(h[x],h[i]+1);
        if(h[i]>=h[son[x]])son[x]=i;
    }
}
//int wei=0; 
void build(int x,int tp){
    if(x==tp){
        g[x]=s;
        s+=h[x]+1; 
//      wei+=h[x]+1;
    }
    if(son[x])g[son[x]]=g[x]+1,build(son[x],tp);
    for(int i:z[x])if(i!=fa[x]&&i!=son[x])build(i,i); 
}
int a,ans;
void solve(int x){
    for(int i:z[x]){
        if(i!=fa[x])solve(i); 
    }
    g[x][0]=f[x];
    if(h[x])g[x][0]=max(g[x][0],g[x][1]); 
    for(int i:z[x]){
        if(i==fa[x]||i==son[x])continue;
        for(int d=0;d<=h[i];d++){
            while(ans<n){
                int k=max(0,ans-d);
                if(k<=h[x]&&g[x][k]+g[i][d]+a>ans)ans++;
                else break;
            }
        } 
        for(int d=h[i];d>=0;d--){
            g[x][d+1]=max(g[x][d+1],g[i][d]);
        }
        if(h[x])g[x][0]=max(g[x][0],g[x][1]); 
    } 
    while(ans<h[x]&&f[x]+g[x][ans+1]+a>ans)ans++; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        z[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        f[i]=n+1;
        if(z[i].size()==(i==1))p[i]=-1;
    }
    for(int i=n;i>=1;i--){
        if(p[i]==-1)f[i]=0;
        f[fa[i]]=min(f[fa[i]],f[i]+1);
    }   
    dfs(1); 
    build(1,1);
    int q;
    cin>>q;
    while(q--){
        cin>>a;
        ans=0;
        solve(1);
        cout<<ans<<' '; 
    }
    return 0;
}