題目

https://codeforces.com/gym/105139/problem/I

思路

其實相當于是分別求黑色點和白色點所構成的樹的直徑。
當兩個連通塊連在了一起，假設它們的直徑是 $(u_1,v_1)，(u_2,v_2)$，那么新連通塊的直徑一定是 $(u_1,v_1)，(u_2,v_2)，(v_1,u_2)，(v_1,v_2)，(u_1,u_2)，(u_1,v_2)$ 中的一條。
由于題目要給鏈染色，所以只能樹剖+線段樹維護。
白色的點倒過來求一遍即可。

代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
vector<int> dep,fa,ans,siz,top,mxs,dfn,f,id,tr,tag,ti;
vector<array<int,3>> d;
int n,q,inf,tot;
vector<array<int,2>> Q;
vector<vector<int>> e,p;
int gf(int x)
{return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void dfs1(int u,int fa)
{siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;for(auto v:e[u]){if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[mxs[u]])mxs[u]=v;}
}
void dfs2(int u,int topf)
{dfn[u]=++tot; id[tot]=u;top[u]=topf;if(!mxs[u]) return;dfs2(mxs[u],topf);for(auto v:e[u]){if(v==f[u]||v==mxs[u]) continue;dfs2(v,v);}
}
int lca(int x,int y)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);x=f[top[x]];}if(dep[x]<dep[y]) swap(x,y); return y;
}
int getdis(int u,int v)
{int l=lca(u,v);return dep[u]+dep[v]-2*dep[l]+1;
}
void pushdown(int u)
{if(!tag[u]) return;tag[u<<1]=tag[u<<1|1]=tag[u];tr[u<<1]=tr[u<<1|1]=tag[u];tag[u]=0;
}
void build(int u,int st,int ed)
{if(st==ed){tr[u]=inf;return;}int mid=st+ed>>1;build(u<<1,st,mid); build(u<<1|1,mid+1,ed);
}
void change(int u,int st,int ed,int l,int r,int t)
{if(l<=st&&ed<=r){tag[u]=t;tr[u]=t;return;}pushdown(u);int mid=st+ed>>1;if(mid>=l) change(u<<1,st,mid,l,r,t);if(mid<r) change(u<<1|1,mid+1,ed,l,r,t);
}
int query(int u,int st,int ed,int x)
{if(st==ed&&ed==x){return tr[u];}pushdown(u);int mid=st+ed>>1;if(mid>=x) return query(u<<1,st,mid,x);else return query(u<<1|1,mid+1,ed,x);
}
void dye(int x,int y,int c)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);change(1,1,n,dfn[top[x]],dfn[x],c);x=f[top[x]];}if(dep[x]<dep[y]) swap(x,y); change(1,1,n,dfn[y],dfn[x],c);
}
int merge(int u,int v)
{int x=gf(u),y=gf(v);if(x==y) return 0;auto [u1,v1,d1]=d[x];auto [u2,v2,d2]=d[y];int ur=u1,vr=v1,dr=d1;if(d2>d1){ur=u2; vr=v2; dr=d2;}u=u1; v=u2; int di=getdis(u,v);if(di>dr){ur=u; vr=v; dr=di;}u=u1; v=v2; di=getdis(u,v);if(di>dr){ur=u; vr=v; dr=di;}u=v1; v=u2; di=getdis(u,v);if(di>dr){ur=u; vr=v; dr=di;}u=v1; v=v2; di=getdis(u,v);if(di>dr){ur=u; vr=v; dr=di;}d[x]={ur,vr,dr};fa[y]=x;return dr;
}
void init(int n,int q)
{tot=0;dep.clear(); dep.resize(n+1);fa.clear(); fa.resize(n+1);f.clear(); f.resize(n+1);id.clear(); id.resize(n+1);tr.clear(); tr.resize(n<<2|1);tag.clear(); tag.resize(n<<2|1);for(int i=1; i<=n; i++) fa[i]=i;e.clear(); e.resize(n+1);p.clear(); p.resize(q+2);ti.clear(); ti.resize(n+1);siz.clear(); siz.resize(n+1);top.clear(); top.resize(n+1);mxs.clear(); mxs.resize(n+1);dfn.clear(); dfn.resize(n+1);ans.clear(); ans.resize(q+1);Q.clear(); Q.resize(q+1);
}
void O_o()
{cin>>n>>q;inf=q+1;init(n,q);for(int i=1; i<n; i++){int x,y;cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}dfs1(1,0);dfs2(1,1);build(1,1,n);d.resize(n+1);for(int i=1; i<=n; i++)d[i]={i,i,1};for(int i=1; i<=q; i++){int u,v;cin>>u>>v;Q[i]={u,v};}for(int i=q; i>=1; i--){auto [u,v]=Q[i];dye(u,v,i);}for(int i=1; i<=n; i++){int t=query(1,1,n,dfn[i]);ti[i]=t;p[t].push_back(i);}//solveint mx=1;for(int i=1; i<=q; i++){for(auto u:p[i]){for(auto v:e[u]){if(ti[v]>i) continue;int ass=merge(u,v);mx=max(mx,ass);
//				cerr<<ass<<"**\n\n";}}ans[i]=max(ans[i],mx);}mx=1;for(int i=1; i<=n; i++)d[i]={i,i,1};for(int i=1; i<=n; i++) fa[i]=i;for(int i=q+1; i>=2; i--){for(auto u:p[i]){for(auto v:e[u]){if(ti[v]<i) continue;int ass=merge(u,v);mx=max(mx,ass);
//				cerr<<ass<<"**\n\n";}}ans[i-1]=max(ans[i-1],mx);}for(int i=1; i<=q; i++){cout<<ans[i]<<"\n";}
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(2);int T=1;cin>>T;while(T--){O_o();}
}