给定一棵树，每次可以将一条链到根染成一种新的颜色，对于一条边，它的权值在相邻两个点颜色不同时为1，否则为0。
查询一条路径的边权和，子树里所有点到当前点的距离和，所有路径边权和为0的点对。
链上染色这个操作，很容易就可以想到用\(LCT\)来维护，这个就是\(LCT\)的\(access\)?操作,在进行轻重边转换的时候，相当于我们需要做一个子树加减的操作，这个东西可以用\(dfs\)序类维护。
注意在\(LCT\)加子树的时候要先\(findroot\)找到真正的根，再去加。
#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
int tot,head[N];
int n,q;
ll tr[N<<2],la[N<<2],size[N];
int dfn[N],p[N][21],deep[N];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
struct edge{
int n,to;
}e[N<<1];
inline void add(int u,int v){
e[++tot].n=head[u];
e[tot].to=v;
head[u]=tot;
}
inline void pushdown(int cnt,int l,int r){
int mid=(l+r)>>1;
tr[cnt<<1]+=(mid-l+1)*la[cnt];
tr[cnt<<1|1]+=(r-mid)*la[cnt];
la[cnt<<1]+=la[cnt];
la[cnt<<1|1]+=la[cnt];
la[cnt]=0;
}
void upd(int cnt,int l,int r,int L,int R,int x){
if(l>=L&&r<=R){
tr[cnt]+=x*(r-l+1);
la[cnt]+=x;
return;
}
int mid=(l+r)>>1;
pushdown(cnt,l,r);
if(mid>=L)upd(cnt<<1,l,mid,L,R,x);
if(mid<R)upd(cnt<<1|1,mid+1,r,L,R,x);
tr[cnt]=tr[cnt<<1]+tr[cnt<<1|1];
}
ll query(int cnt,int l,int r,int L,int R){
if(l>=L&&r<=R)return tr[cnt];
pushdown(cnt,l,r);
int mid=(l+r)>>1;ll ans=0;
if(mid>=L)ans+=query(cnt<<1,l,mid,L,R);
if(mid<R)ans+=query(cnt<<1|1,mid+1,r,L,R);
return ans;
}
void clear(int cnt,int l,int r){
tr[cnt]=la[cnt]=0;
if(l==r)return;
int mid=(l+r)>>1;
clear(cnt<<1,l,mid);
clear(cnt<<1|1,mid+1,r);
}
struct LCT{
#define ls c[x][0]
#define rs c[x][1]
int top,c[N][2],fa[N],val[N],rev[N],q[N];
ll dp[N];
void clear(){
for(int i=1;i<=n;++i){
dp[i]=val[i]=rev[i]=fa[i]=c[i][0]=c[i][1]=0;
}
}
inline void pushup(int x){
dp[x]=dp[c[x][0]]+dp[c[x][1]]+1;
}
inline void pushdown(int x){
if(rev[x]){
rev[ls]^=1;rev[rs]^=1;rev[x]^=1;
swap(ls,rs);
}
}
inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
inline bool ge(int x){return c[fa[x]][1]==x;}
inline void rotate(int x){
int y=fa[x],z=fa[y],o=ge(x);
if(!isroot(y))c[z][ge(y)]=x;
fa[x]=z;fa[y]=x;fa[c[x][o^1]]=y;
c[y][o]=c[x][o^1];c[x][o^1]=y;
pushup(y);pushup(x);
}
inline void splay(int x){
top=1;q[top]=x;
for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for(int i=top;i;--i)pushdown(q[i]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y))
if(ge(x)==ge(y))rotate(y);
else rotate(x);
rotate(x);
}
}
inline void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);
int now=c[x][1];
if(now){
now=find(now);
upd(1,1,n,dfn[now],dfn[now]+size[now]-1,1);
}
c[x][1]=y;pushup(x);
if(y){
y=find(y);
upd(1,1,n,dfn[y],dfn[y]+size[y]-1,-1);
}
}
}
inline void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
inline int find(int x){
while(c[x][0])pushdown(x),x=c[x][0];
return x;
}
inline void split(int x,int y){
makeroot(x);access(y);splay(y);
}
inline void link(int x,int y){
makeroot(x);fa[x]=y;
}
inline void cut(int x,int y){
split(x,y);
if(c[y][0]==x&&fa[x]==y&&!c[x][1])c[y][0]=0,fa[x]=0;
pushup(y);
}
}lc;
inline int getlca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=20;i>=0;--i)if(deep[u]-(1<<i)>=deep[v]){
u=p[u][i];
}
if(u==v)return u;
for(int i=20;i>=0;--i)if(p[u][i]!=p[v][i]){
u=p[u][i];
v=p[v][i];
}
return p[u][0];
}
void dfs(int u,int fa){
dfn[u]=++dfn[0];
upd(1,1,n,dfn[u],dfn[u],deep[u]);
size[u]=1;
for(int i=1;i<=20;++i)p[u][i]=p[p[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
deep[v]=deep[u]+1;p[v][0]=u;
lc.fa[v]=u;
dfs(v,u);
size[u]+=size[v];
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
int x,y;
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);
int u,v,opt;
for(int i=1;i<=q;++i){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d",&u,&v);
lc.split(u,v);
}
if(opt==2){
scanf("%d%d",&u,&v);
int lca=getlca(u,v);
int x=query(1,1,n,dfn[u],dfn[u])+query(1,1,n,dfn[v],dfn[v])-2*query(1,1,n,dfn[lca],dfn[lca]);
cout<<query(1,1,n,dfn[u],dfn[u])<<" "<<query(1,1,n,dfn[v],dfn[v]);
cout<<" "<<query(1,1,n,dfn[lca],dfn[lca])<<" "<<lca<<endl;
printf("%d\n",deep[u]+deep[v]-2*deep[lca]-x);
}
}
for(int i=0;i<=n+1;++i){
head[i]=deep[i]=size[i]=dfn[i]=0;
}
clear(1,1,n);
lc.clear();
tot=0;
}
return 0;
}