3531: [Sdoi2014]旅行

Time Limit: 40 Sec  Memory Limit: 512 MB

Submit: 3072  Solved: 1365

[][][]

Description

 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，并记下了途中留宿过

的城市的评级最大值。

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

Input

    输入的第一行包含整数N，Q依次表示城市数和事件数。

    接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的

评级和信仰。

    接下来N-1行每行两个整数x，y表示一条双向道路。

    接下来Q行，每行一个操作，格式如上所述。

Output

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

Sample Input

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

Sample Output

8

9

11

3

HINT

 

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

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

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

 

Source

 

树链剖分，对每个信仰开一个线段树，动态开点

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #define maxn 100005 8 using namespace std; 9 inline int read() { 10 int x=0,f=1;char ch=getchar(); 11 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; 12 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; 13 return x*f; 14 } 15 struct data { 16 int to,next; 17 }e[maxn*2]; 18 int head[maxn],cnt; 19 inline void add(int u,int v) {e[cnt].next=head[u];e[cnt].to=v;head[u]=cnt++;} 20 struct node { 21 int s[2],sum,Max; 22 }t[maxn*20]; 23 int tot,size[maxn],son[maxn],f[maxn],dep[maxn],root[maxn]; 24 inline void dfs(int x,int fa) { 25 size[x]=1,dep[x]=dep[fa]+1; 26 for(int i=head[x];i>=0;i=e[i].next) { 27 int to=e[i].to;if(to==fa) continue; 28 dfs(to,x); 29 size[x]+=size[to]; 30 f[to]=x; 31 if(size[son[x]]
             
              =0;i=e[i].next) { 39 int to=e[i].to;if(to==fa||to==son[x]) continue; 40 dfs1(to,x,to); 41 } 42 } 43 int n,q; 44 inline void pushup(int x) { 45 t[x].Max=max(t[t[x].s[0]].Max,t[t[x].s[1]].Max); 46 t[x].sum=t[t[x].s[0]].sum+t[t[x].s[1]].sum; 47 } 48 inline void update(int &x,int l,int r,int tmp,int d) { 49 if(!x) x=++tot; 50 if(l==r) {t[x].Max=t[x].sum=d;return;} 51 int mid=l+r>>1; 52 if(mid>=tmp) update(t[x].s[0],l,mid,tmp,d); 53 else update(t[x].s[1],mid+1,r,tmp,d); 54 pushup(x); 55 } 56 int _sum=0,_max=0; 57 inline void query(int x,int l,int r,int ql,int qr) { 58 if(!x) return; 59 if(ql<=l&&qr>=r) {_sum+=t[x].sum;_max=max(_max,t[x].Max);return;} 60 int mid=l+r>>1; 61 if(ql<=mid) query(t[x].s[0],l,mid,ql,qr); 62 if(qr>mid) query(t[x].s[1],mid+1,r,ql,qr); 63 } 64 inline void find(int x,int y,int z) { 65 while(top[x]!=top[y]) { 66 if(dep[top[x]]