洛谷3313 [SDOI2014]旅行

access_time    bookmark 题解    comment 0 条评论    省选/NOI-

题意

一棵树,每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留,并获得权值。有如下操作:

  1. 单点修改信仰值
  2. 单点修改权值
  3. 查询 $(x,y)$ 路径上权值和
  4. 查询 $(x,y)$ 路径上权值最大值

其中节点数 $N\le 100000$ ,操作数 $M\le 100000$ ,宗教个数 $C\le 100000$ 。

题解

显然每个宗教需要单独维护,但每个宗教开个线段树空间要爆,所以用动态开点线段树。

剩下就板子了,看注释吧。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[200005];
struct Tree {
    int lson,rson,sum,mx;
} tree[2400005];
int cnt,head[100005],n,m,a,b,tcnt,rt[100005],c[100005];
int dfsord,siz[100005],fa[100005],son[100005],deep[100005],top[100005],id[100005],w[100005],ord[100005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void pushup(int x)
{
    tree[x].sum=tree[tree[x].lson].sum+tree[tree[x].rson].sum;
    tree[x].mx=max(tree[tree[x].lson].mx,tree[tree[x].rson].mx);
}

void update(int &x,int s,int l,int r,int delta) //修改
{
    if (!x) x=++tcnt;
    if (r-l==1) tree[x].sum=tree[x].mx=delta;
    else
    {
        int mid=(l+r)>>1;
        if (s<mid) update(tree[x].lson,s,l,mid,delta);
        else update(tree[x].rson,s,mid,r,delta);
        pushup(x);
    }
}

void del(int &x,int s,int l,int r) //删除
{
    if (!x) return;
    if (r-l==1) tree[x].sum=tree[x].mx=0;
    else
    {
        int mid=(l+r)>>1;
        if (s<mid) del(tree[x].lson,s,l,mid);
        else del(tree[x].rson,s,mid,r);
        pushup(x);
    }
}

int qSum(int x,int l,int r,int tl,int tr) //线段树查询权值和
{
    if (!x) return 0;
    if (l<=tl && r>=tr) return tree[x].sum;
    else
    {
        int mid=(tl+tr)>>1,ans=0;
        if (l<mid) ans+=qSum(tree[x].lson,l,r,tl,mid);
        if (r>mid) ans+=qSum(tree[x].rson,l,r,mid,tr);
        return ans;
    }
}

int qMax(int x,int l,int r,int tl,int tr) //线段树查询最大值
{
    if (!x) return 0;
    if (l<=tl && r>=tr) return tree[x].mx;
    else
    {
        int mid=(tl+tr)>>1,ans=0;
        if (l<mid) ans=max(ans,qMax(tree[x].lson,l,r,tl,mid));
        if (r>mid) ans=max(ans,qMax(tree[x].rson,l,r,mid,tr));
        return ans;
    }
}

void dfs1(int x,int f,int dep) //树剖第一次dfs
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    int mx=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[y]>mx)
        {
            mx=siz[y];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf) //树剖第二次dfs
{
    top[x]=topf;
    id[x]=++dfsord;
    ord[dfsord]=x;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline int qRangeSum(int u,int v,int rel) //树上查询权值和
{
    int ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans+=qSum(rt[rel],id[top[u]],id[u]+1,1,n+1);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    ans+=qSum(rt[rel],id[u],id[v]+1,1,n+1);
    return ans;
}

inline int qRangeMax(int u,int v,int rel) //树上查询权值最大值
{
    int ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans=max(ans,qMax(rt[rel],id[top[u]],id[u]+1,1,n+1));
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    ans=max(ans,qMax(rt[rel],id[u],id[v]+1,1,n+1));
    return ans;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) w[i]=read(),c[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for (int i=1;i<=n;i++) update(rt[c[ord[i]]],i,1,n+1,w[ord[i]]); //建树
    while (m--)
    {
        char ch[2]; scanf("%s",ch); a=read(); b=read();
        if (ch[1]=='C') //修改宗教
        {
            del(rt[c[a]],id[a],1,n+1); //先删除
            c[a]=b;
            update(rt[c[a]],id[a],1,n+1,w[a]); //再添加
        }
        else if (ch[1]=='W')
        {
            del(rt[c[a]],id[a],1,n+1);
            w[a]=b;
            update(rt[c[a]],id[a],1,n+1,w[a]);
        }
        else if (ch[1]=='S') printf("%d\n",qRangeSum(a,b,c[a]));
        else printf("%d\n",qRangeMax(a,b,c[a]));
    }
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。