[SDOI2014]旅行

Author Avatar
ZC 2月 02, 2019
  • 在其它设备中阅读本文章

[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​$行两个整数$W_i,C_i​$依次表示记录开始之前,城市$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 \leq10^5 , C \leq10^5$

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

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

题解

树链剖分+动态开点线段树

标签有主席树的原因大概就是运用了主席树动态开点线段树的思想吧。

这次很幸运,错的地方没找多久就发现了,不过很傻逼,就是线段树求$max$中的递归写成求$sum$忘记改了

刚刚好$ 99 ​$行!

#include<cstdio>
namespace FastIO{struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define Fur(i,x,y) for(register int i=x;i<=y;i++)
#define fl(i,x) for(register int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
int MAX(int x,int y){return x>=y?x:y;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
using namespace std;
#define N 100001
int n,q,sz,w[N],c[N];
int head[N],f[N],siz[N],top[N],d[N],id[N];
int cnt=0,tot=0,s[N*20],mx[N*20],ls[N*20],rs[N*20],RT[N];
#define Z int m=(l+r)>>1
#define pu s[x]=s[ls[x]]+s[rs[x]],mx[x]=MAX(mx[ls[x]],mx[rs[x]])
#define cl s[x]=ls[x]=rs[x]=mx[x]=0
void upd(int L,int v,int l,int r,int &x){
    if(!x)x=++tot;
    if(l==r)return (void)(s[x]=mx[x]=v);
    Z;
    if(L<=m)upd(L,v,l,m,ls[x]);
    else upd(L,v,m+1,r,rs[x]);
    pu;
}
void rm(int L,int l,int r,int &x){
    if(l==r)return (void)(cl,x=0);
    Z;
    if(L<=m)rm(L,l,m,ls[x]);
    else rm(L,m+1,r,rs[x]);
    pu;
    if(!ls[x]&&!rs[x])cl,x=0;
}
int qs(int L,int R,int l,int r,int x){
    if(!x)return 0;
    if(L<=l&&r<=R)return s[x];
    Z;
    return ((L<=m)?qs(L,R,l,m,ls[x]):0)+((R>m)?qs(L,R,m+1,r,rs[x]):0);
}
int qm(int L,int R,int l,int r,int x){
    if(!x)return 0;
    if(L<=l&&r<=R)return mx[x];
    Z;
    return MAX(((L<=m)?qm(L,R,l,m,ls[x]):0),((R>m)?qm(L,R,m+1,r,rs[x]):0));
}
struct eg{int to,nxt;}e[N*2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
void dfs(int x){
    siz[x]=1;
    fl(i,x)
    if(to!=f[x]){
        d[to]=d[x]+1;f[to]=x;
        dfs(to);siz[x]+=siz[to];
    }
}
void bt(int x,int tp){
    top[x]=tp;id[x]=++sz;
    int k=0;
    fl(i,x)if(to!=f[x]&&siz[to]>siz[k])k=to;
    if(!k)return;bt(k,tp);
    fl(i,x)if(!top[to])bt(to,to);
}
int fs(int x,int y){
    int k=c[x],ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])SWAP(x,y);
        ans+=qs(id[top[x]],id[x],1,n,RT[k]);x=f[top[x]];
    }if(id[x]>id[y])SWAP(x,y);
    return ans+qs(id[x],id[y],1,n,RT[k]);
}
int fm(int x,int y){
    int k=c[x],ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])SWAP(x,y);
        ans=MAX(ans,qm(id[top[x]],id[x],1,n,RT[k]));x=f[top[x]];
    }if(id[x]>id[y])SWAP(x,y);
    return MAX(ans,qm(id[x],id[y],1,n,RT[k]));
}
int main(){
    in>>n>>q;
    int x,y;char ch[3];
    Fur(i,1,n)in>>w[i]>>c[i];
    Fur(i,1,n-1)in>>x>>y,add(x,y),add(y,x);
    dfs(1);bt(1,1);
    Fur(i,1,n)upd(id[i],w[i],1,n,RT[c[i]]);
    while(q--){
        in>>ch>>x>>y;
        if(ch[0]=='Q')
            if(ch[1]=='S')out<<fs(x,y)<<"\n";
            else out<<fm(x,y)<<"\n";
        else
            if(ch[1]=='C'){
                rm(id[x],1,n,RT[c[x]]);
                c[x]=y;
                upd(id[x],w[x],1,n,RT[c[x]]);
            }
            else{
                w[x]=y;
                upd(id[x],w[x],1,n,RT[c[x]]);
            }
    }
}