蒟蒻全WA求助

回复帖子

@白青sama 2019-09-21 20:53 回复
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <assert.h>

using namespace std;

const int kmax=1e5+10;

///第一遍DFS处理出来的数据
int sz[kmax],son[kmax],father[kmax],depth[kmax];
///sz[u]:以u为根节点的子树节点数目  son[u]:u的重儿子  father[u]:u的父亲  depth[u]:u的深度

///第二遍DFS处理出来的数据
int rk[kmax],top[kmax],num[kmax];
///rk[u]:u节点的dfs序编号  top[u]:u节点的端点  num[cnt]:dfs序为cnt的节点编号

int n,m,r,p,x,y,cnt,w[kmax];
vector<int> edge[kmax];

namespace tree
{
    int tree[kmax<<2],lazy[kmax<<2];

    void build(int l,int r,int id)
    {
        if(l==r)
        {
            tree[id]=w[num[id]]%p;
            return;
        }
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
        tree[id]=(tree[id<<1]+tree[id<<1|1])%p;
    }

    void pushdown(int l,int r,int id)
    {
        if(!lazy[id]) return;
        lazy[id<<1]+=lazy[id];
        lazy[id<<1|1]+=lazy[id];
        int mid=l+r>>1;
        tree[id<<1]+=(mid-l+1)*lazy[id];
        tree[id<<1|1]+=(r-mid)*lazy[id];
        tree[id<<1]%=p;
        tree[id<<1|1]%=p;
        lazy[id]=0;
    }

    void update(int l,int r,int ll,int rr,long long val,int id)
    {
        if(ll<=l&&r<=rr)
        {
            tree[id]+=val*(r-l+1);
            lazy[id]+=val;
            return;
        }
        pushdown(l,r,id);
        int mid=l+r>>1;
        if(ll<=mid) update(l,mid,ll,rr,val,id<<1);
        if(rr>mid) update(mid+1,r,ll,rr,val,id<<1|1);
        tree[id]=(tree[id<<1]+tree[id<<1|1])%p;
    }

    long long query(int l,int r,int ll,int rr,int id)
    {
        if(ll<=l&&r<=rr) return tree[id];
        pushdown(l,r,id);
        int mid=l+r>>1;
        long long sum=0;
        if(ll<=mid)
        {
            sum+=query(l,mid,ll,rr,id<<1);
            sum%=p;
        }
        if(rr>mid)
        {
            sum+=query(mid+1,r,ll,rr,id<<1|1);
            sum%=p;
        }
        return sum;
    }
}

void dfs_1(int now,int fa)
{
    sz[now]=1;
    father[now]=fa;
    depth[now]=depth[fa]+1;
    for(int i=0;i<edge[now].size();i++)
    {
        int s=edge[now][i];
        if(s!=fa)
        {
            sz[now]+=sz[s];
            if(sz[s]>sz[son[now]]) son[now]=s;
        }
    }
    return;
}

void dfs_2(int now,int _top)
{
    rk[now]=++cnt;
    num[cnt]=now;
    top[now]=_top;
    if(!son[now]) return;
    dfs_2(son[now],_top);
    int len=edge[now].size();
    for(int i=0;i<len;i++)
    {
        int s=edge[now][i];
        if(s==father[now]||s==son[now])continue;
        dfs_2(s,s);
    }
    return;
}

int query(int a,int b)
{
    int ans=0,topa=top[a],topb=top[b];
    while(topa!=topb)
    {
        if(depth[a]<depth[b])
        {
            ans+=tree::query(1,n,rk[topa],rk[a],1);
            ans%=p;
            a=father[topa];
            topa=top[a];
        }
        else
        {
            ans+=tree::query(1,n,rk[topb],rk[b],1);
            ans%=p;
            b=father[topb];
            topb=top[b];
        }
    }
    if(depth[a]<depth[b])
    {
        ans+=tree::query(1,n,rk[a],rk[b],1);
        ans%=p;
    }
    else
    {
        ans+=tree::query(1,n,rk[b],rk[a],1);
        ans%=p;
    }
    return ans;
}

void change(int a,int b,int val)
{
    val%=p;
    int topa=top[a],topb=top[b];
    while(topa!=topb)
    {
        if(depth[topa]<depth[topb]) swap(a,b);
        tree::update(1,n,rk[top[a]],rk[a],val,1);
        a=father[top[a]];
        topa=top[a];
    }
    if(depth[a]>depth[b]) swap(a,b);
    tree::update(1,n,rk[a],rk[b],val,1);
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs_1(r,r);
    dfs_2(r,r);
    tree::build(1,n,1);
    while(m--)
    {
        int k,x,y,z;
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            change(x,y,z);
        }
        else if(k==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",query(x,y));
        }
        else if(k==3)
        {
            scanf("%d%d",&x,&y);
            tree::update(1,n,rk[x],rk[x]+sz[x]-1,y,1);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",tree::query(1,n,rk[x],rk[x]+sz[x]-1,1));
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。