P10238 [yLCPC2024] F. PANDORA PARADOXXX 题解

分析

考虑时光倒流。

对于需要合并的两个连通块 \(x,y\)，其合并之后的最远点对距离一定是合并之前的两组点对中产生的。在合并的时候枚举点对，取距离最大值即可。由于我们是倒着来的，所有连通块的最远点对距离最大值不减，所以能直接在合并之后取最大值。

维护连通块用并查集即可。复杂度 \(O(n\log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	il auto max(auto a,auto b){return (a>b?a:b);}
	il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=5e5+10;
int n,m;
int ne[N<<1],e[N<<1],w[N<<1],h[N],idx;
int fa[N],siz[N],s[N][2];
struct edge{
	int x,y,z;
}E[N];
int d[N],vis[N];
int dep[N],dis[N];
int f[N][25];
int Mx[N];
int ans[N],nowmx;

il void add(int a,int b,int c){
	ne[++idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx;
}
il void dfs(int now,int fa){
	dep[now]=dep[fa]+1,f[now][0]=fa;
	for(re int i=1;i<24;++i) f[now][i]=f[f[now][i-1]][i-1];
	for(re int i=h[now];i;i=ne[i]){
		int j=e[i];if(j==fa) continue;
		dis[j]=dis[now]+w[i];
		dfs(j,now);
	}
	return ;
}
il int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(re int i=23;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(re int i=23;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
il int diss(int a,int b){
	return dis[a]+dis[b]-2*dis[lca(a,b)];
}
il int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
il void merge(int x,int y){
	fa[y]=x;
	int mx=0;
	int now[10]={s[x][0],s[x][1],s[y][0],s[y][1]};
	for(re int i=0;i<4;++i)
	for(re int j=0;j<4;++j){
		int nowx=now[i],nowy=now[j];
		int Dis=diss(nowx,nowy);
		if(Dis>mx){
			mx=Dis,s[x][0]=nowx,s[x][1]=nowy;
			Mx[x]=Dis;
		}
	}
	nowmx=max(nowmx,Mx[x]);
	return ;
}

il void solve(){
	n=rd,m=rd,idx=0,nowmx=0;
	for(re int i=1;i<=n;++i){
		fa[i]=i,siz[i]=s[i][0]=s[i][1]=0;
		s[i][0]=s[i][1]=i;
		h[i]=dep[i]=dis[i]=0;
		ans[i]=0,Mx[i]=0;
		for(re int j=0;j<=24;++j) f[i][j]=0;
		vis[i]=0;
	}
	for(re int i=1;i<n;++i){
		int a=rd,b=rd,c=rd;
		add(a,b,c),add(b,a,c);
		E[i]={a,b,c};
	}
	dfs(1,0);
	for(re int i=1;i<=m;++i)
		d[i]=rd,vis[d[i]]=1;
	for(re int i=1;i<n;++i){
		if(vis[i]) continue;
		int x=E[i].x,y=E[i].y;
		if(dep[x]>dep[y]) swap(x,y);
		merge(find(x),find(y));
	}
	for(re int i=m;i>=1;--i){
		int x=E[d[i]].x,y=E[d[i]].y;
		if(dep[x]>dep[y]) swap(x,y);
		ans[i]=nowmx;
		merge(find(x),find(y));
	}
	for(re int i=1;i<=m;++i) cout<<ans[i]<<"\n";
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int t=rd;while(t--)
	solve();
	return 0;
}