有一棵n个节点的树，每个节点有一个颜色，初始每个节点颜色不相同，且以节点1为根。定义每个点的权值为这个点到根的路径上不同颜色的个数。现在进行m次操作，每次操作为下列三种之一： 1、将x到当前根路径上的所有点染成一种新的颜色； 2、将x到当前根路径上的所有点染成一种新的颜色，并且把这个点设为新的根； 3、查询以x为根的子树中所有点权值的平均值。
首先我们观察到：
每次修改都是一种新的颜色。其实就是一次access操作。那么要统计的答案就是子树中每个点到根路径上虚边的条数+1的平均值。在access的过程中假设一个节点v要接为u的右儿子，那么u的右儿子所代表的子树整体会将权值 +1，而 v 所代表的子树整体会将权值 -1。
由于涉及子树修改，所以lct无法维护，只能用线段树分类乱搞了。 利用dfs序的性质，设新的根为root，当前查询节点为x，那么 x 与 root 存在三种关系。 1. x==root，搞整棵树 2. root 不在 x 的子树内，直接搞**以1为根时**x的子树即可 3. root 在 x 的子树内，设 p 为 x 的亲儿子中包含 root 的节点，那么需要搞的就是整棵树去除掉 p 这棵子树的结果得到的答案了。
其实就是操作二。一一对应就好了。
ps：码题愉快~~~
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=200100;typedef long long ll;int fa[N],c[N][2],rev[N],q[N];int dep[N],a[N][21],h[N],w[N],lst[N],tmp[N];ll sum[N*4];int tag[N*4],sz[N*4];int n,m,tot,x,y,tm,root=1;struct edge{int y,next;}g[N];char s[100];void adp(int x,int y){ g[++tot].y=y; g[tot].next=h[x]; h[x]=tot;}void dfs(int x){ fa[x]=a[x][0];w[x]=++tm; tmp[tm]=tmp[w[a[x][0]]]+1; for (int i=h[x];i;i=g[i].next) if (g[i].y!=a[x][0]){ dep[g[i].y]=dep[x]+1; a[g[i].y][0]=x; dfs(g[i].y); } lst[x]=tm;}/*----------------线段树-------------------*/void pushup(int rt){ sum[rt]=sum[2*rt]+sum[2*rt+1];}void tagg(int rt,int val){ sum[rt]+=(ll)val*sz[rt]; tag[rt]+=val;}void pushdown(int rt){ if (tag[rt]){ tagg(2*rt,tag[rt]); tagg(2*rt+1,tag[rt]); tag[rt]=0; }}void build(int rt,int l,int r){ if (l==r){sum[rt]=tmp[l],sz[rt]=1;return;} int mid=(l+r)>>1; build(2*rt,l,mid);build(2*rt+1,mid+1,r); pushup(rt);sz[rt]=sz[2*rt]+sz[2*rt+1];} void change(int rt,int l,int r,int ll,int rr,int val){ if (ll>rr) return; if (ll==l && r==rr){tagg(rt,val);return;} pushdown(rt); int mid=(l+r)>>1; if (ll<=mid) change(2*rt,l,mid,ll,min(rr,mid),val); if (rr> mid) change(2*rt+1,mid+1,r,max(mid+1,ll),rr,val); pushup(rt);}void change(int rt,int k){ if (rt==root) change(1,1,n,1,n,k); else if (w[root]>w[rt] && w[root]<=lst[rt]){ int t=root; for (int i=20;i>=0;i--) if ((dep[t]-dep[rt]-1)&(1<<i)) t=a[t][i]; change(1,1,n,1,w[t]-1,k); change(1,1,n,lst[t]+1,n,k); } else change(1,1,n,w[rt],lst[rt],k);}ll query(int rt,int l,int r,int ll,int rr){ if (ll>rr) return 0; if (ll==l && r==rr) return sum[rt]; pushdown(rt); int mid=(l+r)>>1;long long res=0; if (ll<=mid) res+=query(2*rt,l,mid,ll,min(mid,rr)); if (rr> mid) res+=query(2*rt+1,mid+1,r,max(mid+1,ll),rr); return res;}long double query(int rt){ if (rt==root) return 1.0*query(1,1,n,1,n)/n; if (w[root]>w[rt] && w[root]<=lst[rt]){ int t=root; for (int i=20;i>=0;i--) if ((dep[t]-dep[rt]-1)&(1<<i)) t=a[t][i]; int size=w[t]-1+n-lst[t]; return 1.0*((query(1,1,n,1,w[t]-1)+query(1,1,n,lst[t]+1,n)))/size; } return 1.0*query(1,1,n,w[rt],lst[rt])/(lst[rt]-w[rt]+1);}/*--------------------线段树-------------------------*/ /*---------------------lct---------------------------*/int isroot(int x){ return c[fa[x]][0]!=x && c[fa[x]][1]!=x;}void push_down(int x){ if (rev[x]){ rev[x]^=1; rev[c[x][0]]^=1; rev[c[x][1]]^=1; swap(c[x][0],c[x][1]); }}void rotate(int x){ int y=fa[x],z=fa[y]; int l,r; if (c[fa[x]][0]==x) l=0; else l=1; r=l^1; if (!isroot(y)) { if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; } fa[x]=z;fa[y]=x; fa[c[x][r]]=y; c[y][l]=c[x][r]; c[x][r]=y;}void splay(int x){ int top=0,t=x; q[++top]=x; while (!isroot(t)){ q[++top]=fa[t]; t=fa[t]; } for (int i=top;i;i--) push_down(q[i]); while (!isroot(x)){ int y=fa[x],z=fa[y]; if (!isroot(y)) { if ((c[z][0]==y)!=(c[y][0]==x)) rotate(x); else rotate(y); } rotate(x); }}int find(int x){ int t=x;push_down(x); while (c[t][0]){ t=c[t][0]; push_down(t); } return t;}void access(int x){ int t=0; while (x){ splay(x); if (c[x][1]) change(find(c[x][1]),1); c[x][1]=t;fa[c[x][1]]=x; if (t) change(find(t),-1); t=x;x=fa[x]; }}void makeroot(int x){ access(x); splay(x); rev[x]^=1; root=x;}/*---------------------lct-----------------------*/int main(){ freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<n;i++){ scanf("%d%d",&x,&y); adp(x,y);adp(y,x); } tmp[1]=1;dfs(1); for (int j=1;j<=20;j++) for (int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1]; build(1,1,n); while (m--){ scanf("%s%d",s,&x); if (s[2]=='L') access(x); if (s[2]=='C') makeroot(x); if (s[2]=='Q') PRintf("%.10Lf/n",query(x)); }}新闻热点
疑难解答
