sdoi是真的舒服QAQ
比较神奇的数据结构上树题233
我们观察这个题的性质 发现将一条到1的路径染色很像LCT的access操作 我们不妨将相同颜色的点放在一个splay里面 然后access的时候 一条重边变成轻边的时候其实是 子树内ans +1 可以理解成原来它和它上面的节点颜色原本是相同的 然后断开边表示颜色不同了 轻边变成重边 子树内ans -1 原因同理 于是我们首先需要LCT来维持树的结构
子树内加减->我会dfs序上线段树！ 于是我们可以用线段树维护子树内答案 询问3就变成了区间rmq
我们剩下了询问2 询问2怎么做呢？ 路径问题！ 树上差分！
我们发现这个“权值”也是满足树上差分的性质的 我们可以对其维护它到1号点的ans记为f[i]
于是第二问的答案就是f[x]+f[y]-2*f[lca]+1 （比较神奇 无论lca的颜色是否存在在路径上都是满足这个差分的）
所以我们最后只需要LCT维护树的形态 然后dfs序上线段树维护f 单点查询&区间查询大小值即可QwQ
附代码。（我的代码真的好看233）
#include#include #include #include #define inf 20021225#define mxn 100010#define lson x<<1#define rson x<<1|1#define fa(x) t[x].fa#define ls(x) t[x].son[0]#define rs(x) t[x].son[1]#define not_root(x) (ls(fa(x))==x||rs(fa(x))==x)#define ll long long#define lg 18using namespace std;struct node{int son[2],fa;bool rev;}t[mxn];struct edge{int to,lt;}e[mxn<<1];int in[mxn],cnt,dep[mxn],dfn[mxn],tot;int ff[mxn],n,sz[mxn],fa[mxn][lg+1],d[mxn];struct Segtree{ int mx[mxn<<2],tag[mxn<<2]; void pushup(int x){mx[x]=max(mx[lson],mx[rson]);} void pushdown(int x) { if(tag[x]) { mx[lson]+=tag[x]; tag[lson]+=tag[x]; mx[rson]+=tag[x]; tag[rson]+=tag[x]; tag[x]=0; } } void build(int x,int l,int r) { if(l==r){mx[x]=ff[d[l]];return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(x); } void modify(int x,int l,int r,int LL,int RR,int v) { if(l>=LL&&r<=RR){mx[x]+=v;tag[x]+=v;return;} int mid=(l+r)>>1;pushdown(x); if(LL<=mid) modify(lson,l,mid,LL,RR,v); if(RR>mid) modify(rson,mid+1,r,LL,RR,v); pushup(x); } int query(int x,int l,int r,int LL,int RR) { if(l>=LL&&r<=RR) return mx[x]; int mid=(l+r)>>1,ans=0;pushdown(x); if(LL<=mid) ans=max(ans,query(lson,l,mid,LL,RR)); if(RR>mid) ans=max(ans,query(rson,mid+1,r,LL,RR)); return ans; } int getans(int x) { return query(1,1,n,dfn[x],dfn[x]); }}T;void add(int x,int y){ e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt; e[++cnt].to=x;e[cnt].lt=in[y];in[y]=cnt;}void rotate(int x){ if(!x||!not_root(x)) return; int f=fa(x),gf=fa(f); int k=rs(f)==x,p=k^1; if(not_root(f)) t[gf].son[t[gf].son[1]==f]=x; t[x].fa=gf;t[f].fa=x; t[f].son[k]=t[x].son[p]; if(t[x].son[p]) t[t[x].son[p]].fa=f; t[x].son[p]=f;}void splay(int x){ while(not_root(x)) { int f=fa(x),gf=fa(f); if(not_root(gf)) (rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f); rotate(x); }}int findroot(int x){ while(ls(x)) x=ls(x); return x;}void access(int x){ int y=0,w; do { splay(x); if(rs(x)) w=findroot(rs(x)),T.modify(1,1,n,dfn[w],dfn[w]+sz[w]-1,1); t[x].son[1]=y; if(rs(x)) w=findroot(rs(x)),T.modify(1,1,n,dfn[w],dfn[w]+sz[w]-1,-1); y=x;x=t[x].fa; }while(x);}void dfs(int x){ ff[x]=dep[x];dfn[x]=++tot;d[tot]=x;sz[x]=1;t[x].fa=fa[x][0]; for(int i=1;i<=lg;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(dep[y]) continue; dep[y]=dep[x]+1;fa[y][0]=x; dfs(y);sz[x]+=sz[y]; }}int jump(int x,int len){ for(int i=0;i<=lg;i++) if(len&(1<