萌新刚学OI俩小时,啥都不会菜死了,树剖过不了样例求助

回复帖子

@小蒟蒻皮皮鱼 2019-09-21 19:11 回复
#include<bits/stdc++.h>
using namespace std;
const int N=100050;
int n,m,r,p;
int head[N],ecnt;
struct edge 
{
    int to,nxt;
}edg[N<<1];
inline void add(int u,int v)
{
    edg[++ecnt].to=v;
    edg[ecnt].nxt=head[u];
    head[u]=ecnt;
}

int val[N],w[N];
int dfn[N],fa[N],top[N],siz[N],son[N],dep[N],cnt;

void dfs1(int u,int f)
{
    son[u]=0;
    siz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(int i=head[u];i;i=edg[i].nxt)
    {
        int v=edg[i].to;
        if(v!=f)
        {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}

void dfs2(int u,int f)
{
    dfn[u]=++cnt;
    w[cnt]=val[u];
    if(son[f]==u) top[u]=top[f];
    else top[u]=u;
    if(son[u]) dfs2(son[u],u);
    for(int i=head[u];i;i=edg[i].nxt)
    {
        int v=edg[i].to;
        if(v!=f&&v!=son[u]) dfs2(v,u);
    }
}

int sum[N<<2];
int tree[N<<2];
int lazy[N<<2];

inline bool cover(int l1,int r1,int l2,int r2)
{
    return l1>=l2&&r1<=r2;
}

inline bool xiangjiao(int l1,int r1,int l2,int r2)
{
    return l2<=r1&&l1<=r2;
}

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

void push_down(int cnt,int l,int r)
{
    int mid=l+r>>1;
    lazy[cnt<<1]+=lazy[cnt];
    lazy[cnt<<1|1]+=lazy[cnt];
    sum[cnt<<1]+=lazy[cnt]*(mid-l+1);
    sum[cnt<<1|1]+=lazy[cnt]*(r-mid);
    lazy[cnt]=0;    
}

void add(int cnt,int l,int r,int nl,int nr,int t)
{
    if(cover(l,r,nl,nr))
    {
        lazy[cnt]+=t;
        sum[cnt]+=(r-l+1)*t;
        return;
    }
    push_down(cnt,l,r);
    int mid=l+r>>1;
    if(xiangjiao(l,mid,nl,nr)) add(cnt<<1,l,mid,nl,nr,t);
    if(xiangjiao(mid+1,r,nl,nr)) add(cnt<<1|1,mid+1,r,nl,nr,t);
    sum[cnt]=sum[cnt<<1]+sum[cnt<<1|1];
}

int query(int cnt,int l,int r,int nl,int nr)
{
    if(cover(l,r,nl,nr)) return sum[cnt];
    int ans=0;
    push_down(cnt,l,r);
    int mid=l+r>>1;
    if(xiangjiao(l,mid,nl,nr)) ans+=query(cnt<<1,l,mid,nl,nr);
    if(xiangjiao(mid+1,r,nl,nr)) ans+=query(cnt<<1|1,mid+1,r,nl,nr);
    return ans;
}
//shenmeguidongxiwoc
int Query(int x,int y)//qujian
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        //if(x) cout<<dep[top[x]]<<" "<<dep[top[y]]<<endl;
        ans+=query(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    ans+=query(1,1,n,dfn[y],dfn[x]);
    return ans;
}

int QUERY(int x)
{
    int ans=0;
    ans=query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
    return ans%p;
}

void Add(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        add(1,1,n,dfn[top[x]],dfn[x],k);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    add(1,1,n,dfn[y],dfn[x],k);
}

void ADD(int x,int k)
{
    add(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(r,0);
    dfs2(r,0);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int t;
        scanf("%d",&t);
        if(t==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            Add(x,y,z);
        }
        if(t==2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",Query(x,y));
        }
        if(t==3)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            ADD(x,y);
        }
        if(t==4)
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",QUERY(x));
        }
    }

}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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