[SDOI2014]旅行

时间：2021-08-12 21:30:43

洛谷 P3313 [SDOI2014]旅行

https://www.luogu.org/problem/show?pid=3313

题目描述

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国*为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

“CC x c“：城市x的居民全体改信了c教；

“CW x w“：城市x的评级调整为w;

“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入输出格式

输入格式：

输入的第一行包含整数N，Q依次表示城市数和事件数。 接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。 接下来Q行，每行一个操作，格式如上所述。

输出格式：

对每个QS和QM事件，输出一行，表示旅行者记下的数字。

输入输出样例

输入样例#1： 
5 6

3 1

2 3

1 2

3 3

5 1

1 2

1 3

3 4

3 5

QS 1 5

CC 3 1

QS 1 5

CW 3 3

QS 1 5

QM 2 4
输出样例#1： 
8

    9

    11

    3

说明

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

树链剖分+动态线段树

树链剖分后，对于每个信仰建立一颗线段树

线段树要动态增加、移动点

注意不要与主席树混淆

主席树是所有的点都要新增，这里只需新增以前没有过的点

线段树的移动点：首先将原位置的节点修改为0，再在新位置增加节点。

实现：只需要在确定点在树中的位置（root数组）时，加一个判断，如果root[]位置有数（这个点已经添加过），cnt不+1（不建立新的点），在这个位置修改，否则建立新的点

#include<cstdio>

#include<algorithm>

#define N 100001

using namespace std;

int grade[N],belief[N],front[N],e_tot,cnt;

int dep[N],son[N],fa[N],bl[N],sz,id[N],root[N];

struct node{int next,to;}e[N*];

int lc[N*],rc[N*],maxx[N*],sum[N*];

int n,m;

inline void add(int u,int v)

{

    e[++e_tot].to=v;e[e_tot].next=front[u];front[u]=e_tot;

    e[++e_tot].to=u;e[e_tot].next=front[v];front[v]=e_tot;

}

void init()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d%d",&grade[i],&belief[i]);

    int u,v;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&u,&v);

        add(u,v);

    }

}

inline void dfs1(int x)

{

    son[x]++;

    for(int i=front[x];i;i=e[i].next)

    {

        if(e[i].to==fa[x]) continue;

        fa[e[i].to]=x;

        dep[e[i].to]=dep[x]+;

        dfs1(e[i].to);

        son[x]+=son[e[i].to];

    }

}

inline void dfs2(int x,int chain)

{

    sz++;int y=;

    id[x]=sz;

    bl[x]=chain;

    for(int i=front[x];i;i=e[i].next)

    {

        if(e[i].to==fa[x]) continue;

        if(son[e[i].to]>son[y]) y=e[i].to;

     }

     if(!y) return;

     dfs2(y,chain);

     for(int i=front[x];i;i=e[i].next)

     {

         if(e[i].to==fa[x]||e[i].to==y) continue;

         dfs2(e[i].to,e[i].to);

     }

}

inline void up(int k)

{

    sum[k]=sum[lc[k]]+sum[rc[k]];

    maxx[k]=max(maxx[lc[k]],maxx[rc[k]]);

}

inline void change(int & y,int l,int r,int x,int w)

{

    if(!y) y=++cnt;

    if(l==r) {sum[y]=maxx[y]=w;return;}

    int mid=l+r>>;

    if(x<=mid) change(lc[y],l,mid,x,w);

    else change(rc[y],mid+,r,x,w);

    up(y);

}

inline int work(int k,int l,int r,int opl,int opr,bool p)

{

    if(l>=opl&&r<=opr)

    {

        if(!p) return sum[k];

        else return maxx[k];

    }

    int mid=l+r>>;

    int a=,b=;

    if(opl<=mid) a=work(lc[k],l,mid,opl,opr,p);

    if(opr>mid) b=work(rc[k],mid+,r,opl,opr,p);

    if(!p) return a+b;

    else return max(a,b);

}

inline void operation(int q,int u,int v,bool p)

{

    int ans=;

    while(bl[u]!=bl[v])

    {

        if(dep[bl[u]]<dep[bl[v]]) swap(u,v);

        if(!p) ans+=work(root[q],,n,id[bl[u]],id[u],p);

        else ans=max(ans,work(root[q],,n,id[bl[u]],id[u],p));

        u=fa[bl[u]];

    }

    if(id[u]>id[v]) swap(u,v);

    if(!p) ans+=work(root[q],,n,id[u],id[v],p);

    else ans=max(ans,work(root[q],,n,id[u],id[v],p));

    printf("%d\n",ans);

}

void solve()

{

    for(int i=;i<=n;i++) change(root[belief[i]],,n,id[i],grade[i]);

    char c[];int x,y;

    for(int i=;i<=m;i++)

    {

        scanf("%s%d%d",c,&x,&y);

        if(c[]=='C')

        {

            if(c[]=='C')

            {

                change(root[belief[x]],,n,id[x],);//先删除原来的点

                belief[x]=y;

                change(root[belief[x]],,n,id[x],grade[x]);//再增加新的点

            }

            else

            {

                change(root[belief[x]],,n,id[x],y);

                grade[x]=y;

            }

        }

        else

        {

            if(c[]=='S') operation(belief[x],x,y,);

            else operation(belief[x],x,y,);

        }

    }

}

int main()

{

    init();

    dfs1();

    dfs2(,);

    solve();

}

1个错误：

在查询的时候，没有先确定好哪个宗教的线段树，调用operation函数过程中，u节点随树链（包含所有节点的树）往上跳，不能保证一定调到同一宗教上，宗教随之改变。

所以要先确定好是哪一颗线段树

相关文章