题目:
调了很久...... 已经懒得写题解了. https://www.cnblogs.com/Zinn/p/10124183.html
线段树和 LCT 是分开的. 线段树的子树一直是相对于 1 号点而言. 线段树上维护的值总是相对于当前的 rt 的.
怎么保证一直是相对于当前 rt 的呢? 发现如果 rt 和 rt'之间的链上全是重边, 则每个子树对于 rt 的答案和对于 rt' 的答案是一样的.
所以在换 rt 的时候先按相对于原 rt 的情况把子树信息维护好, 等到把链都弄成重边之后, 值们自然而然就变成相对于新 rt 的了.
写了区间修改区间查询的树状数组.
注意树状数组的 add( ) 里传的那个 k 应该是 long long 类型!!! 因为有 init( ) , 所以它传的不是 +1 * (int 以内的数) , 还是可能爆 int 的!!!
但为什么总是对拍不出问题? 大概因为自己建的是随机树, 深度期望 log ;i * d[ i ] 的那个 d[ i ] (差分数组) 是对深度的差分, 所以总是拍不出错吧.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define ll long long
- #define ls Ls[cr]
- #define rs Rs[cr]
- using namespace std;
- const int N=1e5+5,K=20;
- int n,hd[N],xnt,to[N<<1],nxt[N<<1],rt;
- int dep[N],fa[N],pre[N][K],c[N][2],dfn[N],siz[N],tot;
- int sta[N],top; ll tmp[N],f[N],fi[N]; bool rev[N];
- int rdn()
- {
- int ret=0;bool fx=1;char ch=getchar();
- while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
- while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
- return fx?ret:-ret;
- }
- void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
- void dfs(int cr)
- {
- dfn[cr]=++tot;siz[cr]=1;
- dep[cr]=dep[fa[cr]]+1;tmp[tot]=dep[cr];
- pre[cr][0]=fa[cr];
- for(int i=1;pre[pre[cr][i-1]][i-1];i++)
- pre[cr][i]=pre[pre[cr][i-1]][i-1];
- for(int i=hd[cr],v;i;i=nxt[i])
- if(!dfn[v=to[i]])
- {
- fa[v]=cr;dfs(v);
- siz[cr]+=siz[v];
- }
- }
- void add(int x,ll k,ll *f){for(;x<=n;x+=(x&-x))f[x]+=k;}//ll k! for init
- ll qry(int x,ll *f){ll ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret;}
- ll qry(int x)
- {
- ll ret=0;int yx=x+1;
- for(;x;x-=(x&-x))ret+=(ll)yx*f[x]-fi[x];return ret;
- }
- void init()
- {
- for(int i=n;i;i--)tmp[i]-=tmp[i-1],add(i,tmp[i],f);
- for(int i=1;i<=n;i++)tmp[i]*=i,add(i,tmp[i],fi);
- }
- void mdfy(int L,int R,int k)
- {
- if(L>R)return;/////
- add(L,k,f);add(R+1,-k,f);
- add(L,k*L,fi);add(R+1,-k*(R+1),fi);
- }
- ll query(int L,int R)
- {
- if(L>R)return 0;///
- ll a=(R+1)*qry(R,f)-qry(R,fi);
- ll b=L*qry(L-1,f)-qry(L-1,fi);
- return a-b;
- }
- bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
- void Rev(int x)
- {
- if(!rev[x])return;rev[x]=0;
- 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],d=(x==c[y][1]);
- if(!isroot(y))c[z][y==c[z][1]]=x;
- fa[x]=z;
- fa[c[x][!d]]=y;fa[y]=x;
- c[y][d]=c[x][!d];c[x][!d]=y;
- }
- void splay(int x)
- {
- sta[top=1]=x;
- for(int k=x;!isroot(k);k=fa[k])sta[++top]=fa[k];
- for(int i=top;i;i--)Rev(sta[i]);
- int y,z;
- while(!isroot(x))
- {
- y=fa[x];z=fa[y];
- if(!isroot(y))
- ((x==c[y][1])^(y==c[z][1]))?rotate(x):rotate(y);
- rotate(x);
- }
- }
- int fnd(int x)
- {Rev(x);while(c[x][0])x=c[x][0],Rev(x);return x;}
- int fnd(int x,int f)
- {
- for(int i=17;i>=0;i--)
- if(dep[pre[x][i]]>dep[f])x=pre[x][i];
- return x;
- }
- bool intree(int x,int rt)
- {return dfn[x]>=dfn[rt]&&dfn[x]<dfn[rt]+siz[rt];}
- void chg(int x,int k)
- {
- if(!intree(rt,x))mdfy(dfn[x],dfn[x]+siz[x]-1,k);
- else
- {
- int d=fnd(rt,x);//d!!
- mdfy(1,dfn[d]-1,k);mdfy(dfn[d]+siz[d],n,k);
- }
- }
- void access(int x)
- {
- int t=0;
- while(x)
- {
- splay(x);
- if(c[x][1])chg(fnd(c[x][1]),1);
- if(t)chg(fnd(t),-1);
- c[x][1]=t;
- t=x;x=fa[x];
- }
- }
- void makeroot(int x)
- {
- access(x);splay(x);rev[x]^=1;rt=x;//rt=x after access(x)
- }
- double query(int x)
- {
- if(x==rt) return (double)query(1,n)/n;
- if(intree(rt,x))
- {
- int d=fnd(rt,x);
- ll ret=query(1,dfn[d]-1)+query(dfn[d]+siz[d],n);
- return (double)ret/(n-siz[d]);
- }
- return (double)query(dfn[x],dfn[x]+siz[x]-1)/siz[x];
- }
- int main()
- {
- n=rdn();int Q=rdn();
- for(int i=1,u,v;i<n;i++)
- {
- u=rdn();v=rdn();add(u,v);add(v,u);
- }
- dfs(1);init();
- char ch[10];int x;rt=1;
- while(Q--)
- {
- scanf("%s",ch);x=rdn();
- if(ch[2]=='L')access(x);
- if(ch[2]=='C')makeroot(x);
- if(ch[2]=='Q')printf("%.10f\n",query(x));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2888663.html