前置知识
解法
正着删边不太可做，考虑离线下来反着加边。
一个显而易见的结论：设点集 \(A\) 的直径的两个端点为 \(u_{1},v_{1}\)，另一个点集 \(B\) 的直径的两个端点为 \(u_{2},v_{2}\)，则 \(A \bigcup B\) 的直径端点一定是 \(\{ u_{1},v_{1},u_{2},v_{2} \}\) 中的两个。
并查集维护连通块内直径的两个端点即可。
手动实现下清空来保证复杂度正确。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
ll siz[200010],fa[200010],dep[200010],dis[200010],son[200010],top[200010],u[200010],v[200010],x[200010],vis[200010],ans[200010],tot=0,sum=0;
vector<pair<ll,ll> >e[200010];
void add(ll u,ll v,ll w)
{
e[u].push_back(make_pair(v,w));
}
void dfs1(ll x,ll father,ll w)
{
siz[x]=1;
fa[x]=father;
dep[x]=dep[father]+1;
dis[x]=dis[father]+w;
for(ll i=0;i<e[x].size();i++)
{
if(e[x][i].first!=father)
{
dfs1(e[x][i].first,x,e[x][i].second);
siz[x]+=siz[e[x][i].first];
son[x]=(siz[e[x][i].first]>siz[son[x]])?e[x][i].first:son[x];
}
}
}
void dfs2(ll x,ll id)
{
top[x]=id;
if(son[x]!=0)
{
dfs2(son[x],id);
for(ll i=0;i<e[x].size();i++)
{
if(e[x][i].first!=son[x]&&e[x][i].first!=fa[x])
{
dfs2(e[x][i].first,e[x][i].first);
}
}
}
}
ll lca(ll u,ll v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]>dep[top[v]])
{
u=fa[top[u]];
}
else
{
v=fa[top[v]];
}
}
return (dep[u]<dep[v])?u:v;
}
ll ask_dis(ll x,ll y)
{
return dis[x]+dis[y]-2*dis[lca(x,y)];
}
struct DSU
{
ll fa[200010],pt[200010][2],tmp[5];
void init(ll n)
{
for(ll i=1;i<=n;i++)
{
fa[i]=i;
pt[i][0]=pt[i][1]=i;
}
}
ll find(ll x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(ll x,ll y)
{
if(dep[x]>dep[y])
{
swap(x,y);
}
x=find(x);
y=find(y);
fa[y]=x;
ll maxx=0;
tmp[1]=pt[x][0];
tmp[2]=pt[x][1];
tmp[3]=pt[y][0];
tmp[4]=pt[y][1];
for(ll i=1;i<=4;i++)
{
for(ll j=i+1;j<=4;j++)
{
if(ask_dis(tmp[i],tmp[j])>maxx)
{
maxx=ask_dis(tmp[i],tmp[j]);
pt[x][0]=tmp[i];
pt[x][1]=tmp[j];
}
}
}
sum=max(sum,maxx);
}
}D;
int main()
{
ll t,n,q,w,i,j;
scanf("%lld",&t);
for(j=1;j<=t;j++)
{
scanf("%lld%lld",&n,&q);
D.init(n);
tot=sum=0;
for(i=1;i<=n;i++)
{
e[i].clear();
son[i]=vis[i]=0;
}
for(i=1;i<=n-1;i++)
{
scanf("%lld%lld%lld",&u[i],&v[i],&w);
add(u[i],v[i],w);
add(v[i],u[i],w);
}
dfs1(1,0,0);
dfs2(1,1);
for(i=1;i<=q;i++)
{
scanf("%lld",&x[i]);
vis[x[i]]=1;
}
for(i=1;i<=n-1;i++)
{
if(vis[i]==0)
{
D.merge(u[i],v[i]);
}
}
for(i=q;i>=1;i--)
{
ans[i]=sum;
D.merge(u[x[i]],v[x[i]]);
}
for(i=1;i<=q;i++)
{
printf("%lld\n",ans[i]);
}
}
return 0;
}