[SDOI2014]旅行

题目

题目描述

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：

输出样例#1：

说明

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

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

题解

有多少个宗教就建几个线段树，这就得用到动态开点了

几个坑点：

数组要开大一点（$1e5\times 32$差不多）

建树时注意树与树之间会重叠

区间查询时只查询与出发点信仰相同的点~~然而样例能过~~

如查询$1\rightarrow 3\rightarrow 5$，$5$与$1$信仰相同，$3$不同，所以$3$不查询

还有单点修改时记得储存，不能只把线段树中的点修改，原点也要修改

然后差不多了，耐着性子打完吧

我打了$198$行还慢的要死……

代码

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm> 
# include<queue>
# include<cmath>
#define mid ((l+r)>>1)
#define tl c[k].l
#define tr c[k].r
#define ini inline int
#define inv inline void
#define ge getchar()
#define is isdigit(ch)
#define cn(a) string a;cin>>a
using namespace std;
const int MAX=1e5+1;
struct p{
    int x,maxn,l,r;
}c[MAX<<5];
struct q{
    int x,y;
}C[MAX<<1];
struct o{
    int deep,id,siz,son,fa,top,w,belief;
}cc[MAX];
int n,m,num,cnt,tot;
int h[MAX],rt[MAX];
ini max(int x,int y)
{
    return x>y?x:y;
}
ini read()
{
    int x=0,f=1;
    char ch=ge;
    while(!is)
    {
        if(ch=='-') f=-1;
        ch=ge;
    }
    while(is)
    {
        x=x*10+ch-48;
        ch=ge;
    }
    return x*f;
}
inv add(int x,int y)
{
    C[++num].x=h[x];
    C[num].y=y;
    h[x]=num;
}
inv pus(int k)
{
    c[k].maxn=max(c[tl].maxn,c[tr].maxn);
    c[k].x=c[tl].x+c[tr].x;
}
void dfs(int x,int f)
{
    cc[x].deep=cc[f].deep+1;
    cc[x].fa=f;
    cc[x].siz=1;
    for(int i=h[x];i;i=C[i].x)
      {
          int y=C[i].y;
          if(y==f) continue;
          dfs(y,x);
          cc[x].siz+=cc[y].siz;
          if(cc[y].siz>cc[cc[x].son].siz)
          cc[x].son=y;
      }
}
void dfs1(int x,int tp)
{
    cc[x].top=tp;
    cc[x].id=++cnt;
    if(cc[x].son) dfs1(cc[x].son,tp);
    for(int i=h[x];i;i=C[i].x)
      {
          int y=C[i].y;
          if(y==cc[x].fa||y==cc[x].son)
          continue;
          dfs1(y,y);
      }
}
void build(int x,int y,int l,int r,int &k)
{
    if(!k) k=++tot;
    if(l==r)
    {
        c[k].maxn=c[k].x=x;
        return;
    }
    if(y<=mid) build(x,y,l,mid,tl);
    else build(x,y,mid+1,r,tr);
    pus(k);
}
void cut(int x,int l,int r,int &k)
{
    if(l==r)
    {
        c[k].maxn=c[k].x=c[k].l=c[k].r=0;
        k=0;
        return;
    }
    if(x<=mid) cut(x,l,mid,tl);
    else cut(x,mid+1,r,tr);
    pus(k);
    if(!tr&&!tl)
    {
        c[k].maxn=c[k].x=c[k].l=c[k].r=0;
        k=0;
    }
}
int ask_max(int l,int r,int k,int L,int R)
{
    if(!k) return 0;
    if(l>=L&&r<=R) return c[k].maxn;
    if(l>R||r<L) return 0;
    return max(ask_max(l,mid,tl,L,R),ask_max(mid+1,r,tr,L,R));
}
int ask_sum(int l,int r,int k,int L,int R)
{
    if(!k) return 0;
    if(l>=L&&r<=R) return c[k].x;
    if(l>R||r<L) return 0;
    return ask_sum(l,mid,tl,L,R)+ask_sum(mid+1,r,tr,L,R);
}
inv CHANGE(int x,int y)
{
    cc[x].w=y;
    build(y,cc[x].id,1,n,rt[cc[x].belief]);
}
inv CUT(int x,int y)
{
    cut(cc[x].id,1,n,rt[cc[x].belief]);
    cc[x].belief=y;
    build(cc[x].w,cc[x].id,1,n,rt[cc[x].belief]);
}
ini ASK_MAX(int x,int y)
{
    int ans=0,RT=cc[x].belief;
    while(cc[x].top!=cc[y].top)
    {
        if(cc[cc[x].top].deep<cc[cc[y].top].deep)
        swap(x,y);
        ans=max(ans,ask_max(1,n,rt[RT],cc[cc[x].top].id,cc[x].id));
        x=cc[cc[x].top].fa;
    }
    if(cc[x].deep>cc[y].deep) swap(x,y);
    ans=max(ans,ask_max(1,n,rt[RT],cc[x].id,cc[y].id));
    return ans;
}
ini ASK_SUM(int x,int y)
{
    int ans=0,RT=cc[x].belief;
    while(cc[x].top!=cc[y].top)
    {
        if(cc[cc[x].top].deep<cc[cc[y].top].deep)
        swap(x,y);
        ans+=ask_sum(1,n,rt[RT],cc[cc[x].top].id,cc[x].id);
        x=cc[cc[x].top].fa;
    }
    if(cc[x].deep>cc[y].deep) swap(x,y);
    ans+=ask_sum(1,n,rt[RT],cc[x].id,cc[y].id);
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
      cc[i].w=read(),cc[i].belief=read();
    for(int i=1;i<n;i++)
      {
          int x=read(),y=read();
          add(x,y);
          add(y,x);
      }
    dfs(1,0);
    dfs1(1,1);
    for(int i=1;i<=n;i++)
      build(cc[i].w,cc[i].id,1,n,rt[cc[i].belief]);
    for(int i=1;i<=m;i++)
      {
          cn(a);
          int x=read(),y=read();
          if(a=="CC")
          CUT(x,y);
          if(a=="CW")
          CHANGE(x,y);
          if(a=="QS")
          printf("%d\n",ASK_SUM(x,y));
          if(a=="QM")
          printf("%d\n",ASK_MAX(x,y));
      }
    return 0;
}

题目