类似于[NOI2021]轻重边的逆过程，操作1即为对$u$执行access（根为1），$dist(u,v)$即为$u$到$v$的虚边数
对前者用LCT维护，并记录轻重边的切换，显然切换总量为$o(nlog n)$
换言之，问题即要支持：
1.修改一条边的边权（实边边权为0，虚边边权为1），共$o(nlog n)$次
2.查询两点间的带权距离
3.查询一个点到子树内所有点的带权距离和
4.查询所有重链长度$l$的$frac{l(l-1)}{2}$之和
关于询问2，将修改边权转换为子树修改和单点查询，并特判lca处即可
关于询问3，即子树内所有边权为1的边的子树大小之和，同样可以子树查询
关于询问4，在切换轻重边时维护即可（即splay的子树大小）
最终，总复杂度为$o(nlog^{2}n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define ll long long 5 #define L (k<<1) 6 #define R (L+1) 7 #define mid (l+r>>1) 8 int E,t,n,m,p,x,y,head[N],dfn[N],sz[N],dep[N],fa[N][20]; 9 ll ans,f[2][N]; 10 struct Edge{ 11 int nex,to; 12 }edge[N<<1]; 13 int lowbit(int k){ 14 return (k&(-k)); 15 } 16 void update(int p,int k,int x){ 17 while (k<=n){ 18 f[p][k]+=x; 19 k+=lowbit(k); 20 } 21 } 22 ll query(int p,int k){ 23 ll ans=0; 24 while (k){ 25 ans+=f[p][k]; 26 k-=lowbit(k); 27 } 28 return ans; 29 } 30 void update(int k,int p){ 31 update(0,dfn[k],p); 32 update(0,dfn[k]+sz[k],-p); 33 update(1,dfn[k],p*sz[k]); 34 } 35 int lca(int x,int y){ 36 if (dep[x]<dep[y])swap(x,y); 37 for(int i=19;i>=0;i--) 38 if (dep[fa[x][i]]>=dep[y])x=fa[x][i]; 39 if (x==y)return x; 40 for(int i=19;i>=0;i--) 41 if (fa[x][i]!=fa[y][i]){ 42 x=fa[x][i]; 43 y=fa[y][i]; 44 } 45 return fa[x][0]; 46 } 47 namespace LCT{ 48 int fa[N],sz[N],ch[N][2]; 49 ll C(int k){ 50 return (ll)k*(k-1)/2; 51 } 52 void clear(){ 53 memset(fa,0,sizeof(fa)); 54 memset(ch,0,sizeof(ch)); 55 for(int i=1;i<=n;i++)sz[i]=1; 56 } 57 bool which(int k){ 58 return ch[fa[k]][1]==k; 59 } 60 bool check(int k){ 61 return ch[fa[k]][which(k)]!=k; 62 } 63 void up(int k){ 64 sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+1; 65 } 66 void rotate(int k){ 67 int f=fa[k],g=fa[f],p=which(k); 68 fa[k]=g; 69 if (!check(f))ch[g][which(f)]=k; 70 fa[ch[k][p^1]]=f,ch[f][p]=ch[k][p^1]; 71 fa[f]=k,ch[k][p^1]=f; 72 up(f),up(k); 73 } 74 void splay(int k){ 75 for(int i=fa[k];!check(k);i=fa[k]){ 76 if (!check(i)){ 77 if (which(i)==which(k))rotate(i); 78 else rotate(k); 79 } 80 rotate(k); 81 } 82 } 83 void get_min(int &k){ 84 while (ch[k][0])k=ch[k][0]; 85 splay(k); 86 } 87 void access(int k){ 88 int lst=0; 89 while (k){ 90 splay(k),ans-=C(sz[k]); 91 if (lst){ 92 get_min(lst); 93 update(lst,-1); 94 } 95 swap(ch[k][1],lst); 96 if (lst){ 97 ans+=C(sz[lst]); 98 get_min(lst); 99 update(lst,1); 100 } 101 up(k),lst=k,k=fa[k]; 102 } 103 ans+=C(sz[lst]); 104 } 105 }; 106 void add(int x,int y){ 107 edge[E]=Edge{head[x],y}; 108 head[x]=E++; 109 } 110 void dfs(int k,int f,int s){ 111 dfn[k]=++dfn[0]; 112 sz[k]=1; 113 dep[k]=s; 114 fa[k][0]=LCT::fa[k]=f; 115 if (!f)fa[k][0]=k; 116 for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1]; 117 for(int i=head[k];i!=-1;i=edge[i].nex) 118 if (edge[i].to!=f){ 119 dfs(edge[i].to,k,s+1); 120 sz[k]+=sz[edge[i].to]; 121 } 122 } 123 int main(){ 124 scanf("%d",&t); 125 while (t--){ 126 scanf("%d%d",&n,&m); 127 E=ans=dfn[0]=0; 128 LCT::clear(); 129 memset(head,-1,sizeof(head)); 130 memset(f,0,sizeof(f)); 131 for(int i=1;i<n;i++){ 132 scanf("%d%d",&x,&y); 133 add(x,y); 134 add(y,x); 135 } 136 dfs(1,0,0); 137 for(int i=2;i<=n;i++)update(i,1); 138 for(int i=1;i<=m;i++){ 139 scanf("%d",&p); 140 if (p==1){ 141 scanf("%d%*d",&x); 142 LCT::access(x); 143 } 144 if (p==2){ 145 scanf("%d%d",&x,&y); 146 printf("%d ",query(0,dfn[x])+query(0,dfn[y])-(query(0,dfn[lca(x,y)])<<1)); 147 } 148 if (p==3){ 149 scanf("%d",&x); 150 printf("%lld ",query(1,dfn[x]+sz[x]-1)-query(1,dfn[x])); 151 } 152 if (p==4)printf("%lld ",ans); 153 } 154 } 155 return 0; 156 }