//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "树链剖分": {
        "prefix": "acm-4.3重链剖分",
        "body": [
            "#include<algorithm>",
            "#include<cstdio>",
            "#define Re register int",
            "using namespace std;",
            "const int N=1e5+3;",
            "int n,m,x,y,z,T,P,op,root,A[N],AA[N];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Killed_Tree{",
            "\tstruct QAQ{int to,next;}a[N<<1];",
            "\tint o,id_o,fa[N],id[N],idx[N],top[N],son[N],size[N],deep[N],head[N];",
            "\tinline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}",
            "\tstruct Segment_Tree{",
            "\t\t#define pl (p<<1)",
            "\t\t#define pr (p<<1|1)",
            "\t\t#define mid (L+R>>1)",
            "\t\tstruct QAQ{int S,l,r,add;}tr[N<<2];",
            "\t\tinline void pushdown(Re p){",
            "\t\t\tRe v=tr[p].add;",
            "\t\t\tif(v){",
            "\t\t\t\t(tr[pl].S+=v*(tr[pl].r-tr[pl].l+1)%P)%=P,(tr[pl].add+=v)%=P;",
            "\t\t\t\t(tr[pr].S+=v*(tr[pr].r-tr[pr].l+1)%P)%=P,(tr[pr].add+=v)%=P;",
            "\t\t\t\ttr[p].add=0;",
            "\t\t\t}",
            "\t\t}",
            "\t\tinline void build(Re p,Re L,Re R){",
            "\t\t\ttr[p].l=L,tr[p].r=R;",
            "\t\t\tif(L==R){tr[p].S=AA[L]%P;return;}",
            "\t\t\tbuild(pl,L,mid),build(pr,mid+1,R);",
            "\t\t\ttr[p].S=(tr[pl].S+tr[pr].S)%P;",
            "\t\t}",
            "\t\tinline void change(Re p,Re l,Re r,Re v){",
            "\t\t\tRe L=tr[p].l,R=tr[p].r;",
            "\t\t\tif(l<=L&&R<=r){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;return;}",
            "\t\t\tpushdown(p);",
            "\t\t\tif(l<=mid)change(pl,l,r,v);",
            "\t\t\tif(r>mid)change(pr,l,r,v);",
            "\t\t\ttr[p].S=(tr[pl].S+tr[pr].S)%P;",
            "\t\t}",
            "\t\tinline int ask(Re p,Re l,Re r){",
            "\t\t\tRe L=tr[p].l,R=tr[p].r;",
            "\t\t\tif(l<=L&&R<=r)return tr[p].S;",
            "\t\t\tRe ans=0;pushdown(p);",
            "\t\t\tif(l<=mid)(ans+=ask(pl,l,r))%=P;",
            "\t\t\tif(r>mid)(ans+=ask(pr,l,r))%=P;",
            "\t\t\treturn ans;",
            "\t\t}",
            "\t}TR;",
            "\tinline void dfs1(Re x,Re Fa){",
            "\t\tsize[x]=1,deep[x]=deep[fa[x]=Fa]+1;",
            "\t\tfor(Re i=head[x],to;i;i=a[i].next)",
            "\t\t\tif((to=a[i].to)!=Fa){",
            "\t\t\t\tdfs1(to,x);",
            "\t\t\t\tsize[x]+=size[to];",
            "\t\t\t\tif(size[to]>size[son[x]])son[x]=to;",
            "\t\t\t}",
            "\t}",
            "\tinline void dfs2(Re x,Re rt){",
            "\t\tid[x]=++id_o,idx[id_o]=x,AA[id_o]=A[x],top[x]=rt;",
            "\t\tif(!son[x])return;//Ҷ�ڵ�",
            "\t\tdfs2(son[x],rt);",
            "\t\tfor(Re i=head[x],to;i;i=a[i].next)",
            "\t\t\tif((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);",
            "\t}",
            "\tinline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt),TR.build(1,1,n);}",
            "\tinline int ask_dis(Re x,Re y){",
            "\t\tRe ans=0;",
            "\t\twhile(top[x]!=top[y]){",
            "\t\t\tif(deep[top[x]]<deep[top[y]])swap(x,y);",
            "\t\t\t(ans+=TR.ask(1,id[top[x]],id[x]))%=P;",
            "\t\t\tx=fa[top[x]];",
            "\t\t}",
            "\t\tif(deep[x]>deep[y])swap(x,y);",
            "\t\t(ans+=TR.ask(1,id[x],id[y]))%=P;",
            "\t\treturn ans;",
            "\t}",
            "\tinline void change_dis(Re x,Re y,Re v){",
            "\t\twhile(top[x]!=top[y]){",
            "\t\t\tif(deep[top[x]]<deep[top[y]])swap(x,y);",
            "\t\t\tTR.change(1,id[top[x]],id[x],v);",
            "\t\t\tx=fa[top[x]];",
            "\t\t}",
            "\t\tif(deep[x]>deep[y])swap(x,y);",
            "\t\tTR.change(1,id[x],id[y],v);",
            "\t}",
            "\tinline int ask_son(Re x){",
            "\t\treturn TR.ask(1,id[x],id[x]+size[x]-1);",
            "\t}",
            "\tinline void change_son(Re x,Re v){",
            "\t\tTR.change(1,id[x],id[x]+size[x]-1,v);",
            "\t}",
            "}T1;",
            "int main(){",
            "\tin(n),in(T),in(root),in(P),m=n-1;",
            "\tfor(Re i=1;i<=n;++i)in(A[i]);",
            "\twhile(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);",
            "\tT1.kill(root);",
            "\twhile(T--){",
            "\t\tin(op);",
            "\t\tif(op<2)in(x),in(y),in(z),T1.change_dis(x,y,z%P);",
            "\t\telse if(op<3)in(x),in(y),printf(\"%d\\n\",T1.ask_dis(x,y));",
            "\t\telse if(op<4)in(x),in(z),T1.change_son(x,z%P);",
            "\t\telse in(x),printf(\"%d\\n\",T1.ask_son(x));",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 树链剖分"
    }
}