思路很简单，但非常考验代码能力
思路
假设对区间[2,8]进行操作
路径由lca 15分成左右俩条链。将左端点2跳到最右上17，对左链17-16-10-15上每个作为左儿子的节点的兄弟操作。
于是构造新树：节点的新父亲为最近异侧祖先的同侧儿子
（手画略丑请忽略）
链上区间操作——树链剖分
一共有三棵树：题目所给原树，构造新树，树链剖分所用线段树
来整合一下需要的操作，便于理清代码思路，并代替行间注释
1、dfs()遍历原树 cnt[]子树所含叶子数，即节点包含区间长度 dep[]深度 Fa[][]倍增求lca
2、Do()连边构造新树
3、树链剖分fhe() Son[]重儿子 siz[]新树子树大小 fa[]新树父亲
che() s[]新树cnt前缀和 dfn[] top[]
4、操作
getlca()
L，R跳到同侧最高
如果L，R都在lca之上，对lca操作，return
如果L在lca之上，对lca左儿子操作，return
树剖[L,lca右儿子)
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+10;
#define int long long
int n,q,x,y,d,op,fa[MAX],son[MAX][2],rt,bro[MAX];
int cnt[MAX],s[MAX];
int Son[MAX],siz[MAX],dfn[MAX],chuo,top[MAX],dep[MAX],Fa[MAX][20];
vector<int>g[MAX];
struct node{
int sum,laz;
} t[MAX<<1];
inline int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
void dfs(int,int);
void Do(int,int,int);
inline int getlca(int,int);
void fhe(int,int);
void che(int,int);
inline void add(int,int,int,int);
inline int ask(int,int,int);
void update(int,int,int,int,int,int);
int query(int,int,int,int,int);
inline void pushdown(int,int,int);
signed main(){
n=read();q=read();
for(int i=1+n;i<2*n;++i){
son[i][0]=read();son[i][1]=read();
bro[son[i][0]]=son[i][1];bro[son[i][1]]=son[i][0];
}for(int i=n+1;i<2*n;++i)
if(!bro[i]){rt=i;break;}
son[0][0]=son[0][1]=rt;bro[rt]=rt;
dfs(rt,rt);Do(rt,0,0);Do(rt,0,1);
fhe(rt,rt);che(rt,rt);
for(int i=2;i<=chuo;++i) s[i]+=s[i-1];
while(q--){
op=read();x=read();y=read();
int lca=getlca(x,y);//
if(x==son[Fa[x][0]][0]) x=bro[fa[x]];
if(y==son[Fa[y][0]][1]) y=bro[fa[y]];
if(op==1){
d=read();
if(dep[x]<=dep[lca]&&dep[y]<=dep[lca]){
update(1,1,2*n-1,dfn[lca],dfn[lca],d);continue;
}add(x,lca,d,0);add(y,lca,d,1);
}else{
if(dep[x]<=dep[lca]&&dep[y]<=dep[lca]){
printf("%lld\n",query(1,1,2*n-1,dfn[lca],dfn[lca]));
continue;
}printf("%lld\n",ask(x,lca,0)+ask(y,lca,1));
}
}
}
void dfs(int u,int f){
dep[u]=dep[f]+1;Fa[u][0]=f;
for(int i=1;(1<<i)<=dep[u];++i) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
if(!son[u][0]){cnt[u]=1;return;}
dfs(son[u][0],u);dfs(son[u][1],u);
cnt[u]=cnt[son[u][0]]+cnt[son[u][1]];
}void Do(int u,int x,int p){
if(!u) return;
if(u==son[Fa[u][0]][p]) g[son[x][p]].push_back(u);
Do(son[u][p],x,p);Do(son[u][p^1],u,p);
}inline int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int h=dep[x]-dep[y];
for(int i=0;i<20;++i)
if(h&(1<<i)) x=Fa[x][i];
if(x==y) return x;
for(int i=19;i>=0;--i)
if(Fa[x][i]!=Fa[y][i]){
x=Fa[x][i];y=Fa[y][i];
}
return Fa[x][0];
}
void fhe(int u,int f){
fa[u]=f;siz[u]=1;
for(int i=0;i<g[u].size();++i){
int v=g[u][i];
fhe(v,u);siz[u]+=siz[v];
if(siz[Son[u]]<siz[v]) Son[u]=v;
}
}void che(int u,int ance){
dfn[u]=++chuo;top[u]=ance;s[chuo]=cnt[u];
if(Son[u]) che(Son[u],ance);
for(int i=0;i<g[u].size();++i)
if(g[u][i]!=Son[u]) che(g[u][i],g[u][i]);
}inline void add(int x,int y,int num,int p){
if(dep[x]<=dep[y]){
update(1,1,2*n-1,dfn[son[y][p]],dfn[son[y][p]],num);
return;
}y=son[y][p^1];
while(top[x]!=top[y]){
update(1,1,2*n-1,dfn[top[x]],dfn[x],num);
x=fa[top[x]];
}update(1,1,2*n-1,dfn[y]+1,dfn[x],num);
}inline int ask(int x,int y,int p){
if(dep[x]<=dep[y])
return query(1,1,2*n-1,dfn[son[y][p]],dfn[son[y][p]]);
y=son[y][p^1];int ans=0;
while(top[x]!=top[y]){
ans+=query(1,1,2*n-1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}ans+=query(1,1,2*n-1,dfn[y]+1,dfn[x]);
return ans;
}
void update(int pos,int l,int r,int ll,int rr,int d){
if(l>=ll&&r<=rr){
t[pos].sum+=(s[r]-s[l-1])*d;
t[pos].laz+=d;return;//
}int mid=l+r>>1;pushdown(pos,s[mid]-s[l-1],s[r]-s[mid]);
if(mid>=ll) update(pos<<1,l,mid,ll,rr,d);
if(mid<rr) update(pos<<1|1,mid+1,r,ll,rr,d);
t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum;
}int query(int pos,int l,int r,int ll,int rr){
if(l>rr||r<ll) return 0;
if(l>=ll&&r<=rr) return t[pos].sum;
int mid=l+r>>1;pushdown(pos,s[mid]-s[l-1],s[r]-s[mid]);
return query(pos<<1,l,mid,ll,rr)+query(pos<<1|1,mid+1,r,ll,rr);
}inline void pushdown(int pos,int l1,int l2){
if(t[pos].laz){
t[pos<<1].sum+=l1*t[pos].laz;t[pos<<1|1].sum+=l2*t[pos].laz;
t[pos<<1].laz+=t[pos].laz;t[pos<<1|1].laz+=t[pos].laz;
t[pos].laz=0;
}
}
View Code
因为线段树懒标记没有+=，调了一下午，原地去世
标签：新树,鸽子,int,MAX,门外,mid,Fa,lca,树上 From： https://www.cnblogs.com/yswn/p/17575955.html