自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:00:02，当前版本为作者最后更新于2024-07-06 18:13:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

LCT 复习就写两题吧，感觉 NOI 不会考。

由于染色操作十分特殊，不难发现：同一类型的病毒，在所有时刻都是连续的。那么一个点所花费的时间，就是它到根路径上颜色连续段的个数。

对于一条边，如果它相连的两个点颜色不同，权值为 $1$，否则为 $0$。则颜色连续段个数就是该节点到根路径权值和加 $1$。

而染色就非常像 $\rm Access$ 操作。因此你可以快速维护权值变化。

唉但是你发现统计答案比较困难 /ll

假设当前的根是 $r$，我们查询了 $u$。

• 如果 $u$ 在以 $1$ 为根的树上不是 $r$ 的祖先

此时 $u$ 的子树和以 $1$ 为根的子树是一样的。

如图。黑色子树内的每条边，它的贡献都是边权 $\times$ 儿子节点的子树大小，而红色树链上的每条边的贡献是边权 $\times$ 黑色子树大小。

求出 LCA 后，可以用树状数组等数据结构维护。

• 如果 $u$ 在以 $1$ 为根的树上是 $r$ 的祖先

我们将所有边分为三类：紫色表示 $u$ 到 $1$ 的路径上的点，红色表示包含 $r$ 的一个 $u$ 儿子的子树内的边，黑色表示其他边。

黑色的边对答案的贡献仍然为边权 $\times$ 儿子节点的子树大小，紫色边对答案的贡献变为边权 $\times$ $(n-$ 儿子节点的子树大小 $)$，红色边只有在 $u$ 到 $r$ 的路径上才会有贡献。

这还是可以用树状数组维护。

捋一捋树状数组维护什么（首先要拍成 DFS 序）

1. 每个点到 $1$ 的权值和与边权 $\times$ 儿子子树大小之和。这样每个边进行修改的时候顺带区间修改即可。

注意整棵树最开始我们认为所有边的边权都是 $1$。可以通过自底向上不断 $\rm Access$ 得到。

2. 子树内边权 $\times$ 儿子子树大小之和。这个可以随手单点修改。

复杂度 $O(n \log n)$，完全没必要树链剖分，但是可能要开 $3$ 个树状数组。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,m,rt=1,tp[MAXN],fa[MAXN][20],dep[MAXN],tot,dfn[MAXN],sze[MAXN];
vector<int> G[MAXN];
struct Node {
	int s[2],fa,flp,l,r;
}t[MAXN];
void flip(int u) {
	return swap(t[u].s[0],t[u].s[1]),t[u].flp^=1,swap(t[u].l,t[u].r),void();
}
void push_down(int u) {
	if(t[u].flp) flip(t[u].s[0]),flip(t[u].s[1]);
	return t[u].flp=0,void();	
}
void push_up(int u) {
	if(t[u].s[0]) t[u].l=t[t[u].s[0]].l; else t[u].l=u;
	if(t[u].s[1]) t[u].r=t[t[u].s[1]].r; else t[u].r=u;
	return ;	
}
int is_root(int u) {
	return u!=t[t[u].fa].s[0]&&u!=t[t[u].fa].s[1];	
}
int get(int u) {
	return u==t[t[u].fa].s[1];	
}
void rotate(int u) {
	int fa=t[u].fa,s=get(u),op=get(fa);
	if(!is_root(fa)) t[t[fa].fa].s[op]=u;t[u].fa=t[fa].fa;
	t[fa].s[s]=t[u].s[s^1],t[t[u].s[s^1]].fa=fa;
	t[u].s[s^1]=fa,t[fa].fa=u;
	return push_up(fa),push_up(u),void();	
}
void PUSH_DOWN(int u) {
	if(!is_root(u)) PUSH_DOWN(t[u].fa);
	return push_down(u),void();	
}
void splay(int u) {
	PUSH_DOWN(u);
	for(int f;f=t[u].fa,!is_root(u);rotate(u)) if(!is_root(f)) rotate(get(u)==get(f)?f:u);
	return ;
}
pair<int,vector<pair<int,int>>> access(int u) {
	int lst=0; vector<pair<int,int>> ans;
	while(u) {
		splay(u);
		if(lst) ans.push_back({t[lst].l,u});
		if(t[u].s[1]) ans.push_back({u,t[t[u].s[1]].l});
		t[u].s[1]=lst,push_up(u),lst=u,u=t[u].fa;
	}
	return {lst,ans};
}
void dfs(int u,int f) {
	t[u].fa=f,dep[u]=dep[f]+1,dfn[u]=++tot,sze[u]=1,fa[u][0]=f;
	ffor(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v:G[u]) if(v!=f) dfs(v,u),sze[u]+=sze[v];
	return ;
}
int jump(int u,int dt) {
	ffor(i,0,19) if(dt&(1<<i)) u=fa[u][i];
	return u;
}
int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	u=jump(u,dep[u]-dep[v]);
	if(u==v) return u;
	roff(i,19,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
struct BIT {
	vector<int> vc;
	void build(int n) {return vc.resize(n+10),void();}
	void update(int pos,int v) {
		while(pos<=n) vc[pos]+=v,pos+=pos&-pos;
		return ;
	}
	int query(int pos) {
		int ans=0;
		while(pos) ans+=vc[pos],pos-=pos&-pos;
		return ans;	
	}
	int query(int l,int r) {
		return query(r)-query(l-1);	
	}
}s1,s2,s3;
void change(int i) {
	if(!tp[i]) {
		tp[i]=1;
		s1.update(dfn[i],1),s1.update(dfn[i]+sze[i],-1);
		s2.update(dfn[i],sze[i]),s2.update(dfn[i]+sze[i],-sze[i]);
		s3.update(dfn[i],sze[i]);
	}
	else {
		tp[i]=0;
		s1.update(dfn[i],-1),s1.update(dfn[i]+sze[i],1);
		s2.update(dfn[i],-sze[i]),s2.update(dfn[i]+sze[i],sze[i]);
		s3.update(dfn[i],-sze[i]);	
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) t[i].l=t[i].r=i;
	ffor(i,1,n-1) {
		int u,v;
		cin>>u>>v,G[u].push_back(v),G[v].push_back(u);	
	}
	dfs(1,0),s1.build(n),s2.build(n),s3.build(n);
	ffor(i,2,n) {
		tp[i]=1;
		s1.update(dfn[i],1),s1.update(dfn[i]+sze[i],-1);
		s2.update(dfn[i],sze[i]),s2.update(dfn[i]+sze[i],-sze[i]);
		s3.update(dfn[i],sze[i]);
	}
	ffor(i,1,m) {
		string S;
		int x;
		cin>>S>>x;
		if(S=="RELEASE") {
			auto vc=access(x).second;
			for(auto pr:vc) {
				int u=pr.first,v=pr.second;
				if(fa[u][0]==v) change(u);
				else change(v);
			}
		}
		else if(S=="RECENTER") {
			auto pr=access(x);
			auto vc=pr.second;
			auto id=pr.first;
			flip(id);
			for(auto pr:vc) {
				int u=pr.first,v=pr.second;
				if(fa[u][0]==v) change(u);
				else change(v);
			}
			rt=x;
		}
		else {
			int ans=0,u=x,r=rt,l=lca(u,r);
			if(l!=u) {
				int cnt_ot=s1.query(dfn[u])+s1.query(dfn[r])-2*s1.query(dfn[l]);
				ans=s3.query(dfn[u]+1,dfn[u]+sze[u]-1)+sze[x]*cnt_ot;
				cout<<fixed<<setprecision(10)<<1.0*ans/sze[u]+1<<'\n';
			}
			else if(r!=u) {
				int kel=jump(r,dep[r]-dep[u]-1);
				int purple=n*s1.query(dfn[u])-2*s2.query(dfn[u]),black=s3.query(n)-s3.query(dfn[kel],dfn[kel]+sze[kel]-1);
				cout<<fixed<<setprecision(10)<<1.0*(purple+black)/(n-sze[jump(r,dep[r]-dep[u]-1)])+1+s1.query(dfn[r])-s1.query(dfn[u])<<'\n';
			}
			else {
				int purple=n*s1.query(dfn[u])-2*s2.query(dfn[u]),black=s3.query(n);
				cout<<fixed<<setprecision(10)<<1.0*(purple+black)/n+1<<'\n';	
			}
		}
	}
	return 0;
}