代码比我的稍微短一点， 提出表扬...
by BriMon @ 2018-06-05 22:46:13
@[刘浩宇（寂）](/space/show?uid=48265) 您好，为啥要强调您刚学OI呢，我很看不起那些强调自己刚学OI来获得偏爱的人，自力更生吧~
by strangers @ 2018-06-05 22:46:47
@[刘浩宇（寂）](/space/show?uid=48265) 您好，为啥要强调您刚学OI呢？
by tarjan @ 2018-06-05 22:50:03
刚学OI就学树链剖分 orz
by YoungNeal @ 2018-06-05 22:53:12
@[刘浩宇（寂）](/space/show?uid=48265) 愚蒟蒻帮大佬您看了一下，发现了少许的错误（但是没有完全解决您的问题，剩下的就看不出了）：以下列出错误：
```cpp
1.题目求的是以r为根节点而不是以1为根节点两个dfs的实参改一下
2.查询子树的各种问题时查询的是以in[u] + siz[u] - 1为下标的节点，一般都是这么做的吧，虽然我不知道您的写法对不对QAQ
3.根节点的父亲不是他自己而是一个虚节点0
4.您忘记%了
5.查询一条路径您的交换写错了吧，我也没仔细看...Orz应该是一个小于，
6.您有没有发现您的seg数组没有用？这个错自己思考（在build里面）
```
剩下的我就看不出了
我这个模板调试了4天
祝大佬好运！
by Chloris @ 2018-06-06 00:13:24
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define REG register
typedef long long ll;
const int maxn=1e6+5;
const int inf=0x3f3f3f3fll;
struct Input{
#define SIZE 20000
char BUF[SIZE],*S,*T;
Input():S(BUF),T(BUF){}
inline char Getchar(){return((S==T)&&(T=(S=BUF)+fread(BUF,1,SIZE,stdin),S==T)?EOF:*S++);}
inline Input&operator>>(char&c){return(c=Getchar(),*this);}
inline Input&operator>>(int&s){
s=0;REG char c;
while(c=Getchar(),c<48||c>57);
while(s=s*10+c-48,c=Getchar(),c>47&&c<58);
return*this;
}inline Input&operator>>(ll&s){
s=0;REG char c;
while(c=Getchar(),c<48||c>57);
while(s=(ll)s*10+c-48,c=Getchar(),c>47&&c<58);
return*this;
}
#undef SIZE
}input;
struct Output{
#define SIZE 20000
char BUF[SIZE],*S,*Limit;
Output():S(BUF),Limit(BUF+SIZE){}
~Output(){fwrite(BUF,1,S-BUF,stdout);}
inline void Flush(){fwrite(BUF,1,S-BUF,stdout);S=BUF;}
inline void Putchar(const char&c){if(S==Limit)Flush();*S++=c;}
inline Output&operator<<(const char&c){return(Putchar(c),*this);}
template<class T>inline Output&operator<<(T s){
static char Stack[20];static int Top;
Top=0;do Stack[++Top]=s%10+48;while(s/=10);
while(Top)Putchar(Stack[Top--]);
return*this;
}
}output;
struct Edge{
int u,v,nxt;
}s[maxn<<2];
int head[maxn],p=0;
int n,m,root,Mod,cnt=0,a[maxn],b[maxn];
int depth[maxn],faa[maxn],son[maxn],tot[maxn],topp[maxn],index[maxn];
inline void add(REG int u,REG int v)
{
s[++p]=(Edge){u,v,head[u]};
head[u]=p;
return;
}
struct Tree{
#define l(a) a<<1
#define r(a) a<<1|1
struct Tree_Node{
int l,r,w,size,add;
Tree_Node(){l=r=w=size=add=0;}
}T[maxn<<2];
inline void update(REG int top)
{
T[top].w=((T[l(top)].w+T[r(top)].w+Mod)%Mod);
return;
}
inline void built(REG int top,REG int l,REG int r)
{
T[top].l=l,T[top].r=r;
T[top].size=r-l+1;
if(l==r) T[top].w=a[l];
else
{
int mid=(l+r)>>1;
built(l(top),l,mid);
built(r(top),mid+1,r);
update(top);
}
return;
}
inline void push_down(REG int top)
{
if(!T[top].add) return;
T[l(top)].w=(T[l(top)].w+T[l(top)].size*T[top].add+Mod)%Mod;
T[r(top)].w=(T[r(top)].w+T[r(top)].size*T[top].add+Mod)%Mod;
T[l(top)].add=(T[l(top)].add+T[top].add)%Mod;
T[r(top)].add=(T[r(top)].add+T[top].add)%Mod;
T[top].add=0;
return;
}
inline void update_add(REG int top,REG int l,REG int r,REG int val)
{
if(l<=T[top].l&&r>=T[top].r)
{
T[top].w+=T[top].size*val;
T[top].add+=val;
}
push_down(top);
int mid=(T[top].l+T[top].r)>>1;
if(l<=mid) update_add(l(top),l,mid,val);
if(r>mid) update_add(r(top),mid+1,r,val);
update(top);
return;
}
inline int Query(REG int l,REG int r,REG int top)
{
int ans=0;
if(l<=T[top].l&&r>=T[top].r) return T[top].w;
push_down(top);
int mid=(T[top].l+T[top].r)>>1;
if(l<=mid) ans=(ans+Query(l,mid,l(top)))%Mod;
if(r>mid) ans=(ans+Query(mid+1,r,r(top)))%Mod;
return ans;
}
}lwd;
inline int dfs1(REG int top,REG int fa,REG int dep)
{
depth[top]=dep;
faa[top]=fa;
tot[top]=1;
int maxson=-1;
for(REG int i=head[top];i;i=s[i].nxt)
{
if(s[i].v==fa) continue;
tot[top]+=dfs1(s[i].v,top,dep+1);
if(tot[s[i].v]>maxson) maxson=tot[s[i].v],son[top]=s[i].v;
}
return tot[top];
}
inline void dfs2(REG int top,REG int fa)
{
index[top]=++cnt;
a[cnt]=b[top];
topp[top]=fa;
if(!son[top]) return;
dfs2(son[top],fa);
for(REG int i=head[top];i;i=s[i].nxt)
{
if(!index[s[i].v]) dfs2(s[i].v,s[i].v);
}
}
inline void Tree_Add(REG int x,REG int y,REG int val)
{
while(topp[x]!=topp[y])
{
if(depth[topp[x]]<depth[topp[y]]) swap(x,y);
lwd.update_add(1,index[topp[x]],index[x],val);
x=faa[topp[x]];
}
if(depth[x]>depth[y]) swap(x,y);
lwd.update_add(1,index[x],index[y],val);
return;
}
inline void Tree_Sum(REG int x,REG int y)
{
int ans=0;
while(topp[x]!=topp[y])
{
if(depth[topp[x]]<depth[topp[y]]) swap(x,y);
ans=(ans+lwd.Query(index[topp[x]],index[x],1))%Mod;
x=faa[topp[x]];
}
if(depth[x]>depth[y]) swap(x,y);
ans=(ans+lwd.Query(index[x],index[y],1))%Mod;
output<<ans<<'\n';
}
int main()
{
input>>n>>m>>root>>Mod;
for(REG int i=1;i<=n;i++)
input>>b[i];
int c,d;
for(int i=1;i<n;i++)
{
input>>c>>d;
add(c,d),add(d,c);
}
dfs1(root,0,1);
dfs2(root,root);
lwd.built(1,1,n);
while(m--)
{
int opt,x,y,z;
input>>opt;
if(opt==1)
{
input>>x>>y>>z;
z%=Mod;
Tree_Add(x,y,z);
}
else if(opt==2)
{
input>>x>>y;
Tree_Sum(x,y);
}
else if(opt==3)
{
input>>x>>z;
lwd.update_add(1,index[x],index[x]+tot[x]-1,z%Mod);
}
else if(opt==4)
{
input>>x;
output<<lwd.Query(index[x],index[x]+tot[x]-1,1)<<'\n';
}
}
return 0;
}
```
by Explorer_CYC @ 2018-06-06 10:25:05
捕获红名蒟蒻*1……
by bztMinamoto @ 2018-06-10 21:05:50