P7735 [NOI2021] 轻重边
题传
树剖不好维护边权，考虑下放到深度深的结点上。
操作一改成：
对于路径
(a, b) 上的所有结点，将其子节点染成轻点，随后将路径上的所有点染成重点，特别地，\text{LCA}(a, b) 为轻点。
拆成两种操作：
-
路径染重/轻；
-
子节点染轻。
操作顺序为
操作三一脸树剖的样子，操作四。。
我们考虑再转化一下题意，我们发现，操作 3/4 中处理的关键是
找到链上有多少颜色相同的点！！1
既然一次操作是 0/1 染色，不妨改为染 时间戳
操作 1 变成区间覆盖。
操作 2 让我们统计相邻相等的数量，但是
不难发现，我们每次查询的区间为
注意多测清空 ，因为这个卡了好久。
Code：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mo=19940417;
const int R=20;
inline int read(){
char ch=getchar();int x=0, f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
namespace Solution{
const int N=2e5+5;
int n, m;
struct node{
node(){st=ed=len=tag=ans=0;}
int st, ed, len, tag, ans;
}d[N*4];
node add(node a, node b){
node c;
c.len=a.len+b.len;
c.ans=a.ans+b.ans+(a.ed==b.st);
c.st=a.st, c.ed=b.ed;
return c;
}
int tot, h[N], dfn[N], cnt, top[N], son[N], fa[N], siz[N], dep[N];
struct Edge{
int to, nxt;
}edge[N*2];
void add(int x, int y){
edge[++tot].to=y, edge[tot].nxt=h[x];
h[x]=tot;return ;
}
void dfs1(int x, int f){
siz[x]=1;
for(int i=h[x]; i; i=edge[i].nxt){
int to=edge[i].to;if(to==f) continue;
dep[to]=dep[x]+1, fa[to]=x, dfs1(to, x);
siz[x]+=siz[to];if(siz[son[x]]<siz[to]) son[x]=to;
}
return ;
}
void dfs2(int x, int root){
// printf("`````%d %d\n", x, root);
top[x]=root, dfn[x]=++cnt;
if(son[x]) dfs2(son[x], root);
for(int i=h[x]; i; i=edge[i].nxt){
int to=edge[i].to;
if(top[to]) continue;
dfs2(to, to);
}
return ;
}
struct SegmentTree{
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)
void pushup(int k){d[k]=add(d[ls], d[rs]);return ;}
void upd(int k, int v){
d[k].ans=d[k].len-1, d[k].st=d[k].ed=v;
d[k].tag=v;return ;
}
void pushdown(int k){
if(!d[k].tag) return ;
upd(ls, d[k].tag), upd(rs, d[k].tag);
d[k].tag=0;
return ;
}
void build(int k, int l, int r){
d[k].len=r-l+1, d[k].tag=d[k].ans=0;
if(l==r){d[k].st=d[k].ed=l&r;return ;}
build(ls, l, mid), build(rs, mid+1, r);
return pushup(k);
}
void change(int k, int l, int r, int x, int y, int v){
if(x<=l&&r<=y) return upd(k, v);pushdown(k);
if(x<=mid) change(ls, l, mid, x, y, v);
if(mid<y) change(rs, mid+1, r, x, y, v);
return pushup(k);
}
node query(int k, int l, int r, int x, int y){
// printf("%d %d %d %d %d\n", k, l, r, x, y);
if(x<=l&&r<=y) return d[k];pushdown(k);
if(y<=mid) return query(ls, l, mid, x, y);
if(x>mid) return query(rs, mid+1, r, x, y);
return add(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
}
#undef ls
#undef rs
#undef mid
}Chtholly;
void change(int x, int y, int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x, y);
Chtholly.change(1, 1, n, dfn[top[x]], dfn[x], v);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x, y);
Chtholly.change(1, 1, n, dfn[x], dfn[y], v);
return ;
}
int LCA(int x, int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x, y);
// printf(">>>%d %d\n", x, y);
x=fa[top[x]];
}
return dep[x]>dep[y]?y:x;
}
int query(int x, int f){
node ret;
while(top[x]!=top[f]){
ret=add(Chtholly.query(1, 1, n, dfn[top[x]], dfn[x]), ret);
x=fa[top[x]];
}
return add(Chtholly.query(1, 1, n, dfn[f], dfn[x]), ret).ans;
}
int ask(int x, int y){
int lca=LCA(x, y);//printf("----%d\n", lca);
return query(x, lca)+query(y, lca);
}
signed work(){
memset(h, 0, sizeof(h)), tot=cnt=0;
memset(fa, 0, sizeof(fa));
memset(son, 0, sizeof(son));
memset(top, 0, sizeof(top));
memset(dep, 0, sizeof(dep));
memset(dfn, 0, sizeof(dfn));
memset(siz, 0, sizeof(siz));
n=read(), m=read();
for(int i=1, a, b; i<n; i++)
a=read(), b=read(), add(a, b), add(b, a);
dfs1(dep[1]=1, 0), dfs2(1, 1);
Chtholly.build(1, 1, n);//Chtholly.debug();
// for(int i=1; i<=n; i++)
// printf("->%d %d\n", dep[i], fa[i]);
for(int i=1; i<=m; i++){
int opt=read(), x=read(), y=read();
if(opt&1) change(x, y, i+n);
else printf("%d\n", ask(x, y));
}
return 0;
}
}
signed main(){
int T=read();
while(T--)
Solution :: work();
return 0;
}