刚学萌新一天的C++求助!

回复帖子

@_tqr 2019-10-06 19:25 回复

闲来无事重打板子的时候发现居然打错了!qwq

麻烦帮忙康康吧!

#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define mid ((l+r)>>1)
#define len (r-l+1)
using namespace std;

int n,m,root,mod,u,v,w,opt,x,y,z;
int a[N];

struct Edge
{
    int next,to;
}edge[N<<1];
int cnt=0,head[N];

inline void add_edge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
} 

/*树链剖分的两个dfs*/

int dep[N],fa[N],size[N],son[N];
void dfs1(int u,int f)
{
    fa[u]=f;
    size[u]=1;
    dep[u]=dep[f]+1;
    for(register int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==f) continue;
        dfs1(v,u);
        size[u]=size[v]+1;
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

int zcnt=0,seg[N],rev[N],top[N];
void dfs2(int u)
{
    int v=son[u];
    if(v)
    {
        seg[v]=++zcnt;//每个点新的编号 
        rev[zcnt]=v;
        top[v]=top[u];//这个点所在链的顶端 
        dfs2(v);
    }
    for(register int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!top[v])
        {
            seg[v]=++zcnt;
            rev[zcnt]=v;
            top[v]=v;
            dfs2(v);
        }
    }
}

/*线段树部分*/

int sum[N<<2],add[N<<2];

void pushup(int rt) {sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;}//向上更新线段树 

void add_add(int rt,int l,int r,int v)//加法标记更新 
{
    add[rt]=(add[rt]+v)%mod;
    sum[rt]=(sum[rt]+v*len)%mod;
}

void pushdown(int rt,int l,int r)//标记下放
{
    if(!add[rt]) return;
    add_add(rt<<1,l,mid,add[rt]);
    add_add(rt<<1|1,mid+1,r,add[rt]);
    add[rt]=0;//记得清零 
}

void modify(int rt,int l,int r,int x,int y,int v)//调整  
{
    if(l>y||r<x) return;
    if(x<=l&&y>=r)
    {
        add_add(rt,l,r,v);
        return;
    }
    pushdown(rt,l,r);
    modify(rt,l,mid,x,y,v);
    modify(rt,mid+1,r,x,y,v);
    pushup(rt);
}

int query(int rt,int l,int r,int x,int y)//求和
{
    if(l>y||r<x) return 0;
    if(x<=l&&y>=r) return sum[rt]%mod;
    return ( query(rt,l,mid,x,y) + query(rt,mid+1,r,x,y) )%mod;
}

void build(int rt,int l,int r)//建树 
{
    if(l==r)
    {
        sum[rt]=a[rev[l]];
        return;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

/*主体部分*/

void modify_edge(int x,int y,int v)//链修改 
{
    int fx=top[x];
    int fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])
        {
            swap(fx,fy);
            swap(x,y);
        }
        modify(1,1,zcnt,seg[fx],seg[x],v);
        x=fa[fx];
        fx=top[x];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1,1,zcnt,seg[x],seg[y],v);
}

int ask_edge(int x,int y)//链查询
{
    int fx=top[x];
    int fy=top[y];
    int res=0;
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])
        {
            swap(fx,fy);
            swap(x,y);
        }
        res=(res+query(1,1,zcnt,seg[fx],seg[x]))%mod;
        x=fa[fx];
        fx=top[x];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=(res+query(1,1,zcnt,seg[x],seg[y])%mod);
    return res;
}

void modify_tree(int rt,int v)//树修改
{
    modify(1,1,zcnt,seg[rt],seg[rt]+size[rt]-1,v%mod);
}

int ask_tree(int rt)//树查询 
{
    return query(1,1,zcnt,seg[rt],seg[rt]+size[rt]-1)%mod;
}

void init()
{
    seg[0]=seg[root]=1;
    top[root]=root;
    rev[1]=root;
    dfs1(root,0);
    dfs2(root);
    build(1,1,seg[0]);
}

int main()
{
    read(n);read(m);read(root);read(mod);
    for(register int i=1;i<=n;++i) read(a[i]),a[i]%=mod;
    for(register int i=1;i<=n-1;++i)
    {
        read(u);read(v);
        add_edge(u,v);
        add_edge(v,u);
    }
    init();
    for(register int i=1;i<=m;++i)
    {
        read(opt);
        if(opt==1)//链增加 
        {
            read(x);read(y);read(z);
            modify_edge(x,y,z);
        }
        else if(opt==2)//链查询最小值 
        {
            read(x);read(y);
            printf("%d\n",ask_edge(x,y));
        }
        else if(opt==3)//树增加 
        {
            read(x);read(z);
            modify_tree(x,z);
        }
        else if(opt==4)//树求和 
        {
            read(x);
            printf("%d\n",ask_tree(x));
        }
    }
    return 0;
}
@_tqr 2019-10-06 20:00 回复 举报

暂时发现的错误:

  1. modify和query的递归写错了
  2. dfs1里面应该是size[u]+=size[v];
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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