深入理解access
(n,min[1,1e5])
我想的一个树链剖分做法：
操作1，单点+1
操作2，(fa[x],fa[y])链求和+2
操作3：子树内链求和最大值
用上树上差分思想，相当于区间加，单点求值，区间求最大值
但这样还有一个漏洞，每次修改时，这条链上的加全部要清空，考虑再开一个线段树，叶子节点代表这个点在树上距离最近的又+1的祖先是谁，修改时一次向上找就好，做到单点查询/修改，子树取(max)
时间复杂度(O(nlog_n^2))
SOL：（对于(access)更深的理解）
染色都染到顶点，有点像(LCT)里的(access)
一个点到根节点的颜色数=这个点到根节点的虚链数+1=(dis[x])
操作2：(ans=dis[x]+dis[y]-dis[lca(x,y)]*2+1)
操作1：每次access是变换虚实边两次，对相应子树造成+1/-1的影响，用线段树维护（注意LCT一个连通块里深度最小的节点才是对应子树的根）
操作3：线段树区间求最大值
时间复杂度(O(nlog_n^2))
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4;
int n,m,tim;
int dep[N],pos[N],st[N],ed[N],fa[N][18];
vector<int>e[N];
namespace seg{
#define lc (p<<1)
#define rc (p<<1|1)
int lz[N<<2],t[N<<2];
inline void pushdown(int p){
if(!lz[p])return;
t[lc]+=lz[p];lz[lc]+=lz[p];
t[rc]+=lz[p];lz[rc]+=lz[p];
lz[p]=0;
}
void build(int p,int l,int r){
if(l==r){t[p]=dep[pos[l]];return;}
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
t[p]=max(t[lc],t[rc]);
}
void modify(int p,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
t[p]+=v;
lz[p]+=v;
return;
}
pushdown(p);
int mid=l+r>>1;
if(ql<=mid)modify(lc,l,mid,ql,qr,v);
if(mid<qr)modify(rc,mid+1,r,ql,qr,v);
t[p]=max(t[lc],t[rc]);
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[p];
pushdown(p);
int mid=l+r>>1,ret=0;
if(ql<=mid)ret=max(ret,query(lc,l,mid,ql,qr));
if(mid<qr)ret=max(ret,query(rc,mid+1,r,ql,qr));
return ret;
}
}
namespace lct{
#define lc ch[p][0]
#define rc ch[p][1]
int ch[N][2],fa[N];
inline bool getson(int p){
return ch[fa[p]][1]==p;
}
inline bool isroot(int p){
return ch[fa[p]][getson(p)]!=p;
}
inline void rotate(int p){
int f=fa[p],g=fa[f],r=getson(p);
if(!isroot(f))ch[g][getson(f)]=p;fa[p]=g;
ch[f][r]=ch[p][r^1];if(ch[f][r])fa[ch[f][r]]=f;
ch[p][r^1]=f;fa[f]=p;
}
inline void splay(int p){
for(;!isroot(p);rotate(p))
if(!isroot(fa[p]))rotate(getson(p)==getson(fa[p])?fa[p]:p);
}
inline int findrt(int p){
while(lc)p=lc;
return p;
}
inline void access(int p){
for(int pre=0,x;p;pre=p,p=fa[p]){
splay(p);
if(rc){
x=findrt(rc);
seg::modify(1,1,n,st[x],ed[x],1);
}
if(pre){
x=findrt(pre);
seg::modify(1,1,n,st[x],ed[x],-1);
}
rc=pre;
}
}
}
void dfs(int x){
st[x]=++tim;
pos[tim]=x;
dep[x]=dep[fa[x][0]]+1;
for(int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto v:e[x]){
if(v==fa[x][0])continue;
lct::fa[v]=fa[v][0]=x;
dfs(v);
}
ed[x]=tim;
}
inline int LCA(int u,int v){
if(dep[u]<dep[v])u^=v^=u^=v;
for(int i=17;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
if(u==v)return u;
for(int i=17;i>=0;i--)
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];v=fa[v][i];
}
return fa[u][0];
}
int main(){
n=read();m=read();
for(int i=1,u,v;i<n;i++){
u=read();v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1);
seg::build(1,1,n);
while(m--){
static int op,x,y,lca,a1,a2,a3;
op=read();x=read();
if(op==1)lct::access(x);
else if(op==2){
y=read();
lca=LCA(x,y);
a1=seg::query(1,1,n,st[x],st[x]);
a2=seg::query(1,1,n,st[y],st[y]);
a3=seg::query(1,1,n,st[lca],st[lca]);
cout<<a1+a2-(a3<<1)+1<<"
";
}
else cout<<seg::query(1,1,n,st[x],ed[x])<<"
";
}
return (0-0);
}