题面: 权限题, 去网上看题面吧.
解析
这题可能是出题人比着 LCT 出的吧...
发现每一次的 RELEASE 与 access 操作极为神似, RECENTER 更是贴心的为你附加了一次 RELEASE,
这不就是 makeroot 中的一次 access 吗... 那我们考虑统计答案, 发现就是那一个点到当前根节点之间虚边的数量, 那么我们用树状数组维护, 每一次将对应的子树在 \(dfs\) 序上连续的一段 + 1 或 - 1 即可.
代码
- #include<cstdio>
- #include<cstdlib>
- #include<iostream>
- #define N 100005
- #define lc c[x][0]
- #define rc c[x][1]
- #define LL long long
- using namespace std;
- const int nlog=16;
- inline int In(){
- char c=getchar(); int x=0,ft=1;
- for(;c<'0'||c>'9';c=getchar()) if(c=='-') ft=-1;
- for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
- return x*ft;
- }
- int n,m,h[N],e_tot=0;
- struct E{ int to,nex; }e[N<<1];
- inline void add(int u,int v){
- e[++e_tot]=(E){v,h[u]}; h[u]=e_tot;
- e[++e_tot]=(E){u,h[v]}; h[v]=e_tot;
- }
- LL sum1[N],sum2[N];
- inline int LB(int x){ return x&(-x); }
- inline void Add1(int x,int C){
- for(int i=x;i<=n;i+=LB(i)) sum1[i]+=C;
- }
- inline LL Sum1(int x){
- LL res=0;
- for(int i=x;i;i-=LB(i)) res+=sum1[i];
- return res;
- }
- inline void Add2(int x,int C){
- for(int i=x;i<=n;i+=LB(i)) sum2[i]+=C;
- }
- inline LL Sum2(int x){
- LL res=0;
- for(int i=x;i;i-=LB(i)) res+=sum2[i];
- return res;
- }
- inline void Modify(int L,int R,int C){
- Add1(L,C); Add1(R+1,-C); Add2(L,C*L); Add2(R+1,-C*(R+1));
- }
- inline LL Query(int L,int R){
- return 1ll*(R+1)*Sum1(R)-Sum2(R)-1ll*L*Sum1(L-1)+Sum2(L-1);
- }
- int sz[N],dfn[N],dfs_clock=0,f[N];
- int fa[N][nlog+5],d[N];
- void dfs(int u,int pre,int dep){
- dfn[u]=++dfs_clock; sz[u]=1; fa[u][0]=pre; d[u]=dep;
- for(int i=1;i<=nlog;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
- for(int i=h[u],v;i;i=e[i].nex){
- v=e[i].to; if(v==pre) continue;
- f[v]=u; dfs(v,u,dep+1); sz[u]+=sz[v];
- }
- Modify(dfn[u],dfn[u]+sz[u]-1,1);
- }
- inline int LCA(int x,int y,int& pos){
- if(d[x]<d[y]) swap(x,y);
- int delta=d[x]-d[y]-1;
- for(int i=nlog;~i;--i) if(delta&(1<<i)) x=fa[x][i];
- if(fa[x][0]==y) return fa[pos=x][0];
- else x=fa[x][0];
- for(int i=nlog;~i;--i) if(fa[x][i]!=fa[y][i]){
- x=fa[x][i]; y=fa[y][i];
- }
- return fa[pos=x][0];
- }
- int c[N][2],r[N],rt;
- inline bool nrt(int x){
- return c[f[x]][0]==x||c[f[x]][1]==x;
- }
- inline void PushDown(int x){
- if(r[x]){ swap(lc,rc); r[lc]^=1; r[rc]^=1; r[x]=0; }
- }
- inline void Modify(int x,int C){
- PushDown(x);
- while(lc) PushDown(lc),x=lc;
- int y,lca=LCA(x,rt,y);
- if(lca!=x) Modify(dfn[x],dfn[x]+sz[x]-1,C);
- else Modify(1,dfn[y]-1,C),Modify(dfn[y]+sz[y],n,C);
- }
- inline double Query(int x){
- int y,lca=LCA(x,rt,y);
- if(lca!=x) return 1.0*Query(dfn[x],dfn[x]+sz[x]-1)/sz[x];
- else return 1.0*(Query(1,dfn[y]-1)+Query(dfn[y]+sz[y],n))/(n-sz[y]);
- }
- inline void rotate(int x){
- int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
- if(nrt(y)) c[z][c[z][1]==y]=x; c[x][!k]=y; c[y][k]=w;
- if(w) f[w]=y; f[y]=x; f[x]=z;
- }
- inline void PushAll(int x){
- if(nrt(x)) PushAll(f[x]);
- PushDown(x);
- }
- inline void splay(int x){
- PushAll(x); int y;
- while(nrt(x)){
- if(nrt(y=f[x])) rotate((c[f[y]][1]==y)^(c[y][1]==x)?x:y);
- rotate(x);
- }
- }
- inline void access(int x){
- for(int y=0;x;x=f[y=x]){
- splay(x);
- if(rc) Modify(rc,1);
- rc=y; if(rc) Modify(rc,-1);
- }
- }
- inline void makeroot(int x){
- access(x); splay(x); r[x]^=1; rt=x;
- }
- int main(){
- n=In(); m=In(); char str[10];
- for(int i=1;i<n;++i) add(In(),In());
- rt=1; dfs(1,0,0);
- for(int i=1,x;i<=m;++i){
- scanf("%s",str); x=In();
- if(str[2]=='L') access(x);
- if(str[2]=='C') makeroot(x);
- if(str[2]=='Q') printf("%.10lf\n",Query(x));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2993127.html