RT ，搞了一天，求教
(已经对着以前的AC代码看过，除了码风有些改变，和变量名不同，膜的位置，其它几乎一样)
附以前AC代码
```
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define int int
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x*=10,x+=c^48,c=getchar();
return x*f;
}
//INT PART
const int N=10000002;
int val[N];
int head[N],num_edge;
struct Edge{int next,to;}edge[N];
int n,m,Mod;
int dep[N],fa[N],siz[N],son[N];
int pos[N],wei[N],top[N],cnt=0;
//FUNCTION
inline void add_edge(int from,int to)
{
edge[++num_edge].to=to;
edge[num_edge].next=head[from];
head[from]=num_edge;
return;
}
//线段树
struct Tr{int l,r,val,lazy;}tr[N<<2];
void build(int rt,int l,int r)
{
tr[rt].l=l,tr[rt].r=r,tr[rt].lazy=0;
if(l==r) {tr[rt].val=wei[l]%Mod;return;}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].val=(tr[rt<<1].val+tr[rt<<1|1].val)%Mod;
return;
}
void change(int rt,int delta)
{
tr[rt].val+=(tr[rt].r-tr[rt].l+1)*delta%Mod;
tr[rt].lazy+=delta%Mod;
return;
}
void push_down(int rt)
{
change(rt<<1,tr[rt].lazy%Mod);
change(rt<<1|1,tr[rt].lazy%Mod);
tr[rt].lazy=0;
return;
}
void update_tree(int rt,int x,int y,int delta)
{
if(tr[rt].l>=x&&tr[rt].r<=y)
{
tr[rt].val+=(tr[rt].r-tr[rt].l+1)*delta%Mod;
tr[rt].lazy+=delta%Mod;
return;
}
if(tr[rt].lazy) push_down(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(x<=mid) update_tree(rt<<1,x,y,delta);
if(y>mid) update_tree(rt<<1|1,x,y,delta);
tr[rt].val=(tr[rt<<1].val+tr[rt<<1|1].val)%Mod;
return;
}
int find(int rt,int x,int y)
{
if(tr[rt].l>=x&&tr[rt].r<=y)
return tr[rt].val%Mod;
int sum=0;
if(tr[rt].lazy)push_down(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(x<=mid) sum+=find(rt<<1,x,y);
if(y>mid) sum+=find(rt<<1|1,x,y);
return sum%Mod;
}
//上面线段树
//下面是树链剖分
//dfs1
/*
标记每个点的深度dep[]
标记每个点的父亲fa[]
标记每个非叶子节点的子树大小(含它自己)
标记每个非叶子节点的重儿子编号son[]
*/
void dfs1(int x,int father,int deep)
{
dep[x]=deep;
fa[x]=father;
siz[x]=1;
int Maxson=0;
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(to==father) continue;
dfs1(to,x,deep+1);
siz[x]+=siz[to];
if(siz[to]>Maxson)
Maxson=siz[to],son[x]=to;
}
return;
}
//dfs2
/*
标记每个点的新编号pos[]
赋值每个点的初始值到新编号上wei[]
处理每个点所在链的顶端top[]
处理每条链
*/
void dfs2(int x,int topn)
{
pos[x]=++cnt;
wei[cnt]=val[x]%Mod;
top[x]=topn;
if(!son[x])return;
dfs2(son[x],topn);
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(to==fa[x]||to==son[x]) continue;
dfs2(to,to);
}
return;
}
//query
int query(int x,int y)
{
int sum=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
sum+=find(1,pos[top[x]],pos[x]); ///注意这个顺序
sum%=Mod;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y); ///
sum+=find(1,pos[x],pos[y]);
return sum%Mod;
}
//一棵树的所有儿子及自己的和
int query_son(int x) //find sons' sum
{
return find(1,pos[x],pos[x]+siz[x]-1);
}
void update_son(int x,int delta)
{
update_tree(1,pos[x],pos[x]+siz[x]-1,delta);
}
//Update
void update_link(int x,int y,int k)
{
k%=Mod;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update_tree(1,pos[top[x]],pos[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update_tree(1,pos[x],pos[y],k);
}
int main()
{
ios::sync_with_stdio(false);
int k,x,y,ty,root;
n=read(),m=read(),root=read(),Mod=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1;i<n;++i)
{x=read(),y=read();add_edge(x,y),add_edge(y,x);}
dfs1(root,0,1);dfs2(root,root);
build(1,1,n);
while(m--)
{
ty=read();
if(ty==1)
{
x=read(),y=read(),k=read();
update_link(x,y,k);
}
else
if(ty==2)
{
x=read(),y=read();
cout<<query(x,y)%Mod<<endl;
}
else if(ty==3)
{
x=read(),y=read();
update_son(x,y);
}
else
{
x=read();
cout<<query_son(x)%Mod<<endl;
}
}
return 0;
}
```
以前还写过一个结构体版本的，也A了，现在不知道怎么回事
6.2.5507.400
系统词频: 20190102
组词数据: 20190102
辅助码 : 20180614
编译时间: 2019-05-13 13:38:21
by lsy263 @ 2019-07-12 00:25:48
@[lsy263](/space/show?uid=72611) 前排Orz数据结构神仙
by disangan233 @ 2019-07-12 07:57:22
@[lsy263](/space/show?uid=72611) 您有一个地方好像打错了……
by Bitter_ @ 2019-07-12 08:27:16
您的LCA_upd的while里面第一个判断错了，我改了之后A了
by Bitter_ @ 2019-07-12 08:28:15
Orz树剖大佬
by 澪lane @ 2019-07-12 08:31:51
@[R_h_DP](/space/show?uid=208881) 错哪里了啊（雾
by Frozencode @ 2019-07-12 08:41:48
@[Frozencode](/space/show?uid=64166)
```cpp
if(dep[top[x]<dep[top[y]]])swap(x,y);
```
您看是不是$dep$写错了啊，应该是
```cpp
if(dep[top[x]]<dep[top[y]])swap(x,y);
```
吧？
by Bitter_ @ 2019-07-12 08:44:00
@[R_h_DP](/space/show?uid=208881) 这也能看出来qwq，膜拜
by Frozencode @ 2019-07-12 08:58:39
@[Frozencode](/space/show?uid=64166) orz红名大佬
by Bitter_ @ 2019-07-12 09:02:25
@[R_h_DP](/space/show?uid=208881) （雾）是多了一个``]``么
by lsy263 @ 2019-07-12 16:05:52