自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 23:11:38，当前版本为作者最后更新于2025-03-24 11:40:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树的直径白学了，完全图 MST 白练了！wssb 嘤嘤嘤！

先考虑没有修改怎么做。

Part 1

答案可以表示为 $\sum far_i-d$，$d$ 表示直径的长度，$far_i$ 表示 $i$ 和最远的点的距离，任意 $far_i$ 一定属于直径两端，但是直径两端相互重复算到所以 $-d$。

考虑证明：这里面的直径两端连边一定不劣，对于剩下的点连入连通块渴望找到最远的点 $far_i$，而 $far_i$ 又可以表示为直径两端点之一，所以一定可以成功连入连通块。

Part 2

如果边权为正，所有的直径中点都是同一个，任意的一个点到最远点都经过直径中点。前面的证明见 oi-wiki，后面显然。

所以说答案可以表示为 $\sum (\frac{d}{2}+dis(i,mid))-d$，至少在没有修改的时候这个是很好求的。

这里的 $mid$ 有可能属于边中间，于是我们把原来的树一条边中间多加一个点变成新树。

Part 3

现在我们加上修改。

如何修改 $d$，可以根据结论一棵树两个点集并起来的直径端点一定在两个点集分别的直径端点这四个点中。

但是现在每次加入的点集只有一个点，所以应该在这三个点中，比个大小就可以轻易求出 $d$，也可以更新出 $mid$。所以我们只用考虑如何求出 $\sum dis(i,mid)$。

有结论新的 $mid$ 和老的最多在新树上面相差一条边，因为如果加入节点 $n+i$ 之后直径长度变大，那么操作给定的 $x$ 一定是其中一条直径的端点，连上 $n+i$ 之后相当于这条直径在新树上面多出了两个点，显然偏移量为 $1$。

$in_k$ 表示新树 $k$ 内部的原点的个数，假设现在是第 $i$ 次操作。

• 直径不变，那么 $\sum dis(i,mid))$ 加上 $n+i$ 的贡献即可。
• 新树上现在的 $mid$ 是原来的儿子，那么 $\sum dis(i,mid))-in_{mid}+(n+i-1-in_{mid})\to \sum dis(i,mid))$。
• 否则一定是原来的父亲，$\sum dis(i,mid))+in_{ymid}-(n+i-1-in_{ymid})\to \sum dis(i,mid))$，$ymid$ 表示原来的 $mid$。

别忘了下面两种情况也要加上 $dis(mid,n+i)$ 即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nn=8e5+5;
int n,q,p[nn],dfn[nn],dis[nn],timer,dep[nn],dad[nn][21],l,r,nwd,mid,dissum,sz[nn];
vector<int> e[nn],nw[nn];
#define pb push_back
struct bit{
	int c[nn];
	inline int lb(int x){return x&(-x);}
	inline void add(int x,int z){
		for(int i=x;i<=((n+q)<<1);i+=lb(i)) c[i]+=z;
	}
	inline int qry(int x){
		int res=0;
		for(int i=x;i>=1;i-=lb(i)) res+=c[i];
		return res;
	}
	inline int query(int l,int r){return qry(r)-qry(l-1);}
}tr;
inline void dfs_pre(int u,int fa){
	dfn[u]=++timer;
	dep[u]=dep[fa]+1;
	dad[u][0]=fa;
	for(int i=1;i<=20;i++) dad[u][i]=dad[dad[u][i-1]][i-1];
	sz[u]=1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs_pre(v,u);
		sz[u]+=sz[v];
	}
}
inline void dfs_getdis(int u,int fa,int &wz){
	if(fa) dis[u]=dis[fa]+1;
	else dis[u]=0;
	if(!wz||dis[wz]<dis[u]) wz=u;
	for(int v:nw[u]){
		if(v==fa) continue;
		dfs_getdis(v,u,wz);
	}
}
inline int fath(int x,int c){
	for(int i=20;i>=0;i--){
		if(c&(1<<i)) x=dad[x][i];
	}
	return x;
}
inline int lca(int u,int v){
	if(dep[u]>dep[v]) swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[dad[v][i]]>=dep[u]) v=dad[v][i];
	}
	if(u==v) return u;
	for(int i=20;i>=0;i--){
		if(dad[u][i]!=dad[v][i]) u=dad[u][i],v=dad[v][i];
	}
	return dad[u][0];
}
inline int getdis(int u,int v){
	return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
inline int getmid(int u,int v){
	if(dep[u]>dep[v]) swap(u,v);
	return fath(v,getdis(u,v)/2);
}
inline void dfs_last(int u,int fa){
	dis[u]=dis[fa]+1;
	if(u<=n+q) dissum+=dis[u],tr.add(dfn[u],1);
	for(int v:nw[u]){
		if(v==fa) continue;
		dfs_last(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	dep[0]=dis[0]=-1;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].pb(i+n+q),e[i+n+q].pb(v);
		e[i+n+q].pb(u),e[v].pb(i+n+q);
		nw[u].pb(i+n+q),nw[i+n+q].pb(v);
		nw[i+n+q].pb(u),nw[v].pb(i+n+q);
	}
	for(int i=1;i<=q;i++){
		cin>>p[i];
		e[i+(n<<1)+q].pb(p[i]),e[n+i].pb(i+(n<<1)+q);
		e[p[i]].pb(i+(n<<1)+q),e[i+(n<<1)+q].pb(n+i);
	}
	dfs_pre(1,0);
	dfs_getdis(1,0,l);
	dfs_getdis(l,0,r);
	nwd=dis[r],mid=getmid(l,r);
	dfs_last(mid,0);
	cout<<(dissum+nwd/2*n-nwd)/2<<endl;
	for(int i=1;i<=q;i++){
		int newl=l,newr=r;
		if(getdis(i+n,l)>getdis(newl,newr)) newl=i+n,newr=l;
		if(getdis(i+n,r)>getdis(newl,newr)) newl=i+n,newr=r;
		if(newl==l&&newr==r){
			dissum+=getdis(mid,i+n);
			cout<<(dissum+nwd/2*(n+i)-nwd)/2<<'\n';
		}
		else{
			l=newl,r=newr;
			nwd=getdis(l,r);
			int prvmid=mid;
			mid=getmid(l,r);
			if(dad[prvmid][0]==mid){
				int sl=tr.query(dfn[prvmid],dfn[prvmid]+sz[prvmid]-1);
				int sy=n+i-1-sl;
				dissum+=sl-sy;
			}
			else{
				int sl=tr.query(dfn[mid],dfn[mid]+sz[mid]-1);
				int sy=n+i-1-sl;
				dissum+=-sl+sy;
			}
			dissum+=getdis(mid,i+n);
			cout<<(dissum+nwd/2*(n+i)-nwd)/2<<'\n';
		}
		tr.add(dfn[i+n],1);
	}
	return 0;
}

具体实现的话其中 $in$ 可以离线求出最终的树的 dfn 用 BIT 做就可以了，也可以同时求出倍增 LCA 数组，由于我们是直接在新树上做的所以最后要除以二。

答案一发对了但是因为作死使用 endl 被卡常了一发！

欢迎补充捉虫！