【Codeforces 516D】Drazil and Morning Exercise | Mrsrz's blog

树的直径，双指针，并查集

题目大意：

给定一棵带权树（权值为正）。定义 $f_i$ 表示 $i$ 到树上离 $i$ 最远的距离。

有 $q$（非常小）次询问，每次给出 $l$，要求在树上选出一个连通块 $S$，使得：

$$(\max_{i\in S}f_i)-(\min_{i\in S} f_i)\leq l$$

需要求出这个连通块中最多有多少个结点。

题解：

在树上距离某个点最远的点，一定是直径的一个端点，所以 $f_i$ 可以通过树形 DP 线性求得。

考虑将 $f_i$ 从大到小排序，然后对每次询问的 $l$，我们用双指针扫描，每次尺取最长的一段，判断这段结点能构成的最大连通块即可。

我们用并查集维护连通块大小，每次新插入一个结点的时候更新答案即可。

有一个问题，这个做法是需要删除点的，如何在并查集上删掉一个点呢？

我们每次删掉的结点 $i$，一定满足 $f_i$ 是当前区间最大的。那么与它相连的点只可能有一个。

也就是说，我们删掉这个点，不会改变其他结点之间的连通性，只会使其所在连通块大小减一。而且之后的操作都和这个点无关。

那么删除的时候只需要将其所在连通块大小减一，别的什么都不用干。

时间复杂度 $O(n\log n+nq\alpha(n))$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,head[N],cnt,m_id[N],u,v,id[N];
LL mx[N],f[N],Len,Dist[N];
int fa[N],sz[N];
bool vis[N];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
struct edge{
    int to,nxt,dis;
}e[N<<1];
inline bool cmp(int a,int b){return f[a]>f[b];}
void DFS(int now,int pre){
    mx[now]=0,m_id[now]=now;
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=pre){
        DFS(e[i].to,now);
        if(mx[now]+mx[e[i].to]+e[i].dis>Len){
            Len=mx[now]+mx[e[i].to]+e[i].dis;
            u=m_id[now],v=m_id[e[i].to];
        }
        if(mx[now]<mx[e[i].to]+e[i].dis){
            mx[now]=mx[e[i].to]+e[i].dis;
            m_id[now]=m_id[e[i].to];
        }
    }
}
void DfS(int now,int pre){
    f[now]=max(f[now],Dist[now]);
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=pre){
        Dist[e[i].to]=Dist[now]+e[i].dis;
        DfS(e[i].to,now);
    }
}
int ans;
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(sz[x]<sz[y])swap(x,y);
    ans=max(ans,sz[x]+=sz[y]),fa[y]=x;
}
void add(int x){
    for(int i=head[x];i;i=e[i].nxt)
    if(vis[e[i].to])merge(x,e[i].to);
    vis[x]=1;
}
inline void erase(int x){
    vis[x]=0;
    --sz[find(x)];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v,w;
        cin>>u>>v>>w;
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    DFS(1,0);
    DfS(u,Dist[u]=0);DfS(v,Dist[v]=0);
    for(int i=1;i<=n;++i)id[i]=i;
    sort(id+1,id+n+1,cmp);
    int q;
    for(cin>>q;q--;){
        LL len;
        cin>>len;
        if(f[id[1]]-f[id[n]]<=len){
            cout<<n<<'\n';
            continue;
        }
        ans=1;
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1,vis[i]=0;
        for(int l=1,r=1;l<=n&&r<=n;++l){
            while(r<=n&&f[id[l]]-f[id[r]]<=len)add(id[r++]);
            erase(id[l]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}