题面：
洛谷P7735
给定一棵\(n\)个点的树，起初所有的边都是轻边。
\(m\)次操作，有两种操作：
1.给一条路径，将与这条路径直接相连的边变成轻边，将这条路径上的边变成重边。
2.给一条路径，问这条路径上有多少条重边。
思路:
这个题有一个非常牛的trick，就是每次一操作后将路径上的点都变成一种新颜色，一条边两端点颜色相同为重边，否则为轻边。然后用树剖线段树维护重边数量和颜色。
代码:
#include<iostream>
using namespace std;
inline int kd(){
int x=0,f=1;
char a=getchar();
while(a<'0'||a>'9'){
if(a=='-'){
f=-1;
}
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
return x*f;
}
int t;
int n,m;
struct node{
int to;
int nxt;
}edge[200010];
int head[100010],tot;
inline void addedge(int u,int v){
edge[++tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
int fa[100010];
int dep[100010];
int sum[100010];
int zs[100010];
int dfn[100010];
int top[100010];
int dui[100010];
int cnt;
inline void dfs1(int u){
sum[u]=1;
zs[u]=0;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u]){
continue;
}
fa[v]=u;
dep[v]=dep[u]+1;
dfs1(v);
sum[u]+=sum[v];
if(sum[v]>sum[zs[u]]){
zs[u]=v;
}
}
}
inline void dfs2(int u,int tp){
top[u]=tp;
dfn[u]=++cnt;
dui[cnt]=u;
if(zs[u]!=0){
dfs2(zs[u],tp);
}
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u]||v==zs[u]){
continue;
}
dfs2(v,v);
}
}
struct nod{
int l,r;
int lz_1;
int lz_2;
int sum;
}tree[400010];
inline void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
tree[i].sum=0;
tree[i].lz_1=-1;
tree[i].lz_2=0;
if(l==r){
return ;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
}
inline void push_down(int i){
if(tree[i].lz_1!=-1){
tree[i*2].lz_1=tree[i].lz_1;
tree[i*2+1].lz_1=tree[i].lz_1;
tree[i*2].sum=tree[i].lz_1*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].sum=tree[i].lz_1*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lz_1=-1;
}
if(tree[i].lz_2!=0){
tree[i*2].lz_2=tree[i].lz_2;
tree[i*2+1].lz_2=tree[i].lz_2;
tree[i].lz_2=0;
}
}
inline void change_1(int i,int l,int r,int p){
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].lz_1=p;
tree[i].sum=p*(tree[i].r-tree[i].l+1);
return ;
}
push_down(i);
if(tree[i*2].r>=l){
change_1(i*2,l,r,p);
}
if(tree[i*2+1].l<=r){
change_1(i*2+1,l,r,p);
}
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
int k;
inline void change_2(int i,int l,int r){
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].lz_2=k;
return ;
}
push_down(i);
if(tree[i*2].r>=l){
change_2(i*2,l,r);
}
if(tree[i*2+1].l<=r){
change_2(i*2+1,l,r);
}
}
inline int search_1(int i,int l,int r){
if(tree[i].l>=l&&tree[i].r<=r){
return tree[i].sum;
}
push_down(i);
int s=0;
if(tree[i*2].r>=l){
s+=search_1(i*2,l,r);
}
if(tree[i*2+1].l<=r){
s+=search_1(i*2+1,l,r);
}
return s;
}
inline int search_2(int i,int p){
if(tree[i].l==tree[i].r){
return tree[i].lz_2;
}
push_down(i);
if(tree[i*2].r>=p){
return search_2(i*2,p);
}
else{
return search_2(i*2+1,p);
}
}
inline void lca_1(int u,int v){
++k;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
if(zs[u]!=0){
change_1(1,dfn[zs[u]],dfn[zs[u]],0);
}
change_1(1,dfn[top[u]],dfn[u],1);
change_2(1,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v]){
swap(u,v);
}
if(zs[u]!=0){
change_1(1,dfn[zs[u]],dfn[zs[u]],0);
}
if(v!=u){
change_1(1,dfn[v]+1,dfn[u],1);
}
change_1(1,dfn[v],dfn[v],0);
change_2(1,dfn[v],dfn[u]);
}
inline int lca_2(int u,int v){
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
if(u!=top[u]){
ans+=search_1(1,dfn[top[u]]+1,dfn[u]);
}
int x=search_2(1,dfn[top[u]]);
if(x!=0){
if(x==search_2(1,dfn[fa[top[u]]])){
ans++;
}
}
u=fa[top[u]];
}
if(dep[u]<dep[v]){
swap(u,v);
}
if(v!=u){
ans+=search_1(1,dfn[v]+1,dfn[u]);
}
return ans;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
head[i]=0;
fa[i]=0;
dep[i]=0;
}
tot=0;
for(int i=1;i<n;i++){
int u,v;
u=kd();v=kd();
addedge(u,v);
addedge(v,u);
}
cnt=0;
dfs1(1);
dfs2(1,1);
build(1,1,n);
k=0;
while(m--){
int opt=kd(),u=kd(),v=kd();
if(opt==1){
lca_1(u,v);
}
else{
printf("%d\n",lca_2(u,v));
}
}
}
return 0;
}