求大佬调树链剖分

提交记录

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+20,MAXX=0x3f3f3f3f;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
int n,m,vis[N],now[N],a[N],son[N],scnt[N],lh[N],id[N],f[N],deg[N],cnt,top[N];
int mark[N*4];
vector<int> ma[N];
struct edge{
    int l,r,sum;
}tr[N*4];
void pushdown(int k)
{
    if(!mark[k]) return;
    tr[k<<1].sum+=mark[k]*(tr[k<<1].r-tr[k<<1].l+1);
    tr[k<<1|1].sum+=mark[k]*(tr[k<<1|1].r-tr[k<<1|1].l+1);
    mark[k<<1]+=mark[k];
    mark[k<<1|1]+=mark[k];
    mark[k]=0;
}
void build(int k,int l,int r)
{
    tr[k].l=l,tr[k].r=r;
    if(l==r) return void(tr[k].sum=lh[l]);
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
void change(int k,int l,int r,int pos)
{
//  cout << pos << ' ' << l << ' ' << r << ' ' <<tr[k].l << ' ' << tr[k].r << ' ' << tr[k].sum << endl;
    if(l<=tr[k].l&&tr[k].r<=r)
    {
        tr[k].sum+=pos*(r-l+1);
        mark[k]+=pos;
        return;
    }
    pushdown(k);
    int mid=(tr[k].l+tr[k].r)>>1;
    if(l<=mid) change(k<<1,l,r,pos);
    if(mid<r) change(k<<1|1,l,r,pos);
    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
int query(int k,int l,int r)
{
    cout << k << ' ' << tr[k].l << ' ' << tr[k].r << ' ' << tr[k].sum << endl;
    if(l<=tr[k].l&&tr[k].r<=r)  return tr[k].sum;
    pushdown(k); 
    int ans=0, mid=(tr[k].l+tr[k].r)>>1;
    if(l<=mid) ans+=query(k<<1,l,r);
    if(mid<r) ans+=query(k<<1|1,l,r);
    return ans;
}

void dfs1(int u,int fa)
{
    f[u]=fa;
    deg[u]=deg[fa]+1;
    scnt[u]=1;
    for(int i=0;i<ma[u].size();i++)
    {
        if(ma[u][i]==fa) continue;
        dfs1(ma[u][i],u);
        if(scnt[son[u]]<=scnt[ma[u][i]]) son[u]=ma[u][i];
        scnt[u]+=scnt[ma[u][i]];
    }
}
void dfs2(int u,int fa,int ftop)
{
//  cout << u << ' ' << cnt <<endl; 
    id[u]=++cnt;
    top[u]=ftop;
    lh[cnt]=a[u];
    if(!son[u]) return;
    dfs2(son[u],u,ftop);
    for(int i=0;i<ma[u].size();i++)
    {
        if(ma[u][i]==fa||ma[u][i]==son[u])continue;
        dfs2(ma[u][i],u,ma[u][i]);
    }
}
int cl2(int x,int y)
{
    int res=0;
    while(top[x]!=top[y])
    {
        if(deg[top[x]]<deg[top[y]]) swap(x,y);
        res+=query(1,id[top[x]],id[x]);
        x=f[top[x]];
    }
    if(deg[x]>deg[y]) swap(x,y);
    res+=query(1,id[x],id[y]);
    return res;
}
void cl1(int x,int y,int z)
{
    int res=0;
    while(top[x]!=top[y])
    {
        if(deg[top[x]]<deg[top[y]]) swap(x,y);
        change(1,id[top[x]],id[x],z);
        x=f[top[x]];
    }
    if(deg[x]>deg[y]) swap(x,y);
    change(1,id[x],id[y],z);
}
int main()
{
    int r,p;
    cin >> n >> m >> r >> p;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin >> x >> y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    } 
    dfs1(r,0);
    dfs2(r,0,r);
    build(1,1,n);
    for(int i=1;i<=n;i++) cout << lh[i] << ' ';
    cout <<endl;
    for(int i=1;i<=n;i++) cout << id[i] << ' ';
    cout <<endl;
    while(m--)
    {
        int op,x,y,z;
        cin >> op;
        if(op==1)
        {
            cin >> x >> y >> z;
            cl1(x,y,z);
        }
        else if(op==2)
        {
            cin >> x >> y;
            cout << cl2(x,y)%p << endl;
        }
        else if(op==3)
        {
            cin >> x >> y;
//          cout << id[x] << ' ' << id[x]+scnt[x]-1 << endl;
            change(1,id[x],id[x]+scnt[x]-1,y);
        }
        else if(op==4)
        {
            cin >> x;
//          cout << id[x] << ' ' << id[x]+scnt[x]-1 << endl;
            cout << query(1,id[x],id[x]+scnt[x]-1)%p << endl;
        }
    }
    return 0;
}
/*
5 5 2 2224
7 3 7 8 0 
1 2
1 5
3 1
4 1
1 2 5 3
4 1
3 1 5
2 1 4
*/