[国家集训队]旅游

题目传送门

题目描述

Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

输入输出格式

输入格式：

输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0...N − 1。

接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1...N − 1。|w| <= 1000。输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。

接下来有M 行，每行描述了一个操作，操作有如下五种形式：

C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。
N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。
SUM u v，表示询问从景点u 到v 所获得的总愉悦度。
MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。
MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。

测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。

输出格式：

对于每一个询问(操作S、MAX 和MIN)，输出答案。

输入输出样例

输入样例#1：

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

输出样例#1：

说明

很容易的基础题哦>.<

　　一道码农题=-=

　　节点记录该节点与父亲之间的边的边权，然后树剖+线段树即可。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #define mid ((l+r)>>1)
  7 using namespace std ;
  8 const int INF = 0x7ffffff ;
  9 const int N = 1e5 + 10 ;
 10 
 11 inline int read() {
 12     int k = 0 , f = 1 ; char c = getchar() ;
 13     for( ; !isdigit(c) ; c = getchar())
 14       if(c == '-') f = -1 ;
 15     for( ; isdigit(c) ; c = getchar())
 16       k = k*10 + c-'0' ;
 17     return k*f ;
 18 }
 19 struct eee {
 20     int x, y ;
 21 }ee[N] ;
 22 inline void add1(int xx,int yy) {
 23     static int cnt = 0 ;
 24     ee[++cnt].x = xx, ee[cnt].y = yy ;
 25 }
 26 
 27 struct Node {
 28     int maxx, minn, sum, laz ;
 29     Node *ls, *rs ;
 30     inline void pushup() {
 31         maxx = max(ls->maxx,rs->maxx) ; minn = min(ls->minn,rs->minn) ;
 32         sum = ls->sum + rs->sum ;
 33     }
 34     inline void pushdown() {
 35         if(!laz) return ;
 36         ls->sum *= -1, rs->sum *= -1 ;
 37         int t = ls->maxx ;
 38         ls->maxx = -ls->minn, ls->minn = -t ;
 39         t = rs->maxx ;
 40         rs->maxx = -rs->minn, rs->minn = -t ;
 41         ls->laz ^= 1 ; rs->laz ^= 1 ;  laz = 0 ;
 42     }
 43 }pool[N<<1], *root ;   int res ;  int wt[N] ;
 44 inline Node *newNode() {
 45     static int cnt = 0 ;
 46     return &pool[++cnt] ;
 47 }
 48 Node *build(int l,int r) {
 49     Node *cur = newNode() ;  cur->laz = 0 ;
 50     if(l == r) {
 51         cur->maxx = cur->minn = cur->sum = wt[l] ;
 52     } else {
 53         cur->ls = build(l,mid) ; cur->rs = build(mid+1,r) ;
 54         cur->pushup() ;
 55     }
 56     return cur ;
 57 }
 58 void change_interval(Node *cur,int l,int r,int a,int b) {
 59     if(l >= a && r <= b) {
 60         cur->laz ^= 1 ;  cur->sum *= -1 ; 
 61         int t = cur->maxx ; cur->maxx = -cur->minn, cur->minn = -t ;
 62         return ;
 63     }
 64     cur->pushdown() ;
 65     if(a <= mid) change_interval(cur->ls,l,mid,a,b) ;
 66     if(b > mid) change_interval(cur->rs,mid+1,r,a,b) ;
 67     cur->pushup() ;
 68 }
 69 void change_point(Node *cur,int l,int r,int k,int x) {
 70     if(l == r) {
 71         cur->sum = cur->maxx = cur->minn = x ; return ;
 72     }
 73     cur->pushdown() ;
 74     if(k <= mid) change_point(cur->ls,l,mid,k,x) ;
 75     else change_point(cur->rs,mid+1,r,k,x) ;
 76     cur->pushup() ;
 77 }
 78 void get_sum(Node *cur,int l,int r,int a,int b) {
 79     if(l >= a && r <= b) {
 80         res += cur->sum ; return ;
 81     }
 82     cur->pushdown() ;
 83     if(a <= mid) get_sum(cur->ls,l,mid,a,b) ;
 84     if(b > mid) get_sum(cur->rs,mid+1,r,a,b) ;
 85 }
 86 void get_max(Node *cur,int l,int r,int a,int b) {
 87     if(l >= a && r <= b) {
 88         res = max(res,cur->maxx) ; return ;
 89     }
 90     cur->pushdown() ;
 91     if(a <= mid) get_max(cur->ls,l,mid,a,b) ;
 92     if(b > mid) get_max(cur->rs,mid+1,r,a,b) ;
 93 }
 94 void get_min(Node *cur,int l,int r,int a,int b) {
 95     if(l >= a && r <= b) {
 96         res = min(res,cur->minn) ; return ;
 97     }
 98     cur->pushdown() ;
 99     if(a <= mid) get_min(cur->ls,l,mid,a,b) ;
100     if(b > mid) get_min(cur->rs,mid+1,r,a,b) ;
101 }
102 
103 struct Edge {
104     int to, nex, val ;
105 }e[N<<1] ;
106 int n ;  int head[N], top[N], fa[N], w[N], dep[N], siz[N], son[N], bl[N], bll[N] ;
107 inline void add_edge(int x,int y,int z) {
108     static int cnt = 0 ;
109     e[++cnt].to = y, e[cnt].nex = head[x], head[x] = cnt, e[cnt].val = z ;
110 }
111 
112 void dfs1(int x,int f,int deep,int vv) {
113     w[x] = vv ; fa[x] = f ; dep[x] = deep ; siz[x] = 1 ;
114     for(int i=head[x];i;i=e[i].nex) {
115         int y = e[i].to ; if(y == f) continue ;
116         dfs1(y,x,deep+1,e[i].val) ; siz[x] += siz[y] ;
117         if(siz[y] > siz[son[x]]) son[x] = y ;
118     }
119 }
120 int cnt = 0 ;
121 void dfs2(int x,int topf) {
122     top[x] = topf ; wt[++cnt] = w[x] ; bl[x] = cnt ;
123     if(!son[x]) return ;
124     dfs2(son[x],topf) ;
125     for(int i=head[x];i;i=e[i].nex) {
126         int y = e[i].to ; if(y == fa[x] || y == son[x]) continue ;
127         dfs2(y,y) ;
128     }
129 }
130 
131 inline void change1() {
132     int x = read()+1, y = read()+1 ;
133     while(top[x] != top[y]) {
134         if(dep[top[x]] < dep[top[y]]) swap(x,y) ;
135         change_interval(root,1,n,bl[top[x]],bl[x]) ;
136         x = fa[top[x]] ;
137     }
138     if(dep[x] > dep[y]) swap(x,y) ;
139     if(bl[x] < bl[y]) change_interval(root,1,n,bl[x]+1,bl[y]) ;
140 }
141 inline void query1() {
142     int x = read()+1, y = read()+1 ;  res = 0 ;
143     while(top[x] != top[y]) {
144         if(dep[top[x]] < dep[top[y]]) swap(x,y) ;
145         get_sum(root,1,n,bl[top[x]],bl[x]) ;
146         x = fa[top[x]] ;
147     }
148     if(dep[x] > dep[y]) swap(x,y) ;
149     if(bl[x] < bl[y]) get_sum(root,1,n,bl[x]+1,bl[y]) ;
150     printf("%d
",res) ;
151 }
152 inline void query2() {
153     int x = read()+1, y = read()+1 ;  res = -INF ;
154     while(top[x] != top[y]) {
155         if(dep[top[x]] < dep[top[y]]) swap(x,y) ;
156         get_max(root,1,n,bl[top[x]],bl[x]) ;
157         x = fa[top[x]] ;
158     }
159     if(dep[x] > dep[y]) swap(x,y) ;
160     if(bl[x] < bl[y]) get_max(root,1,n,bl[x]+1,bl[y]) ;
161     printf("%d
",res) ;
162 }
163 inline void query3() {
164     int x = read()+1, y = read()+1 ;  res = INF ;
165     while(top[x] != top[y]) {
166         if(dep[top[x]] < dep[top[y]]) swap(x,y) ;
167         get_min(root,1,n,bl[top[x]],bl[x]) ;
168         x = fa[top[x]] ;
169     }
170     if(dep[x] > dep[y]) swap(x,y) ;
171     if(bl[x] < bl[y]) get_min(root,1,n,bl[x]+1,bl[y]) ;
172     printf("%d
",res) ;
173 }
174 
175 int main() {
176     n = read() ;
177     for(int i=1;i<n;i++) {
178         int x = read()+1, y = read()+1, z = read() ;
179         add_edge(x,y,z) ; add_edge(y,x,z) ;
180         add1(x,y) ;
181     }
182     dfs1(1,0,1,0) ; dfs2(1,1) ;
183     root = build(1,n) ;
184     for(int i=1;i<n;i++) {
185         int xx = ee[i].x, yy = ee[i].y ;
186         bll[i] = fa[xx] == yy ? xx : yy ;
187     }
188     int m = read() ;  char ss[10] ;
189     while(m--) {
190         scanf("%s",&ss) ;
191         if(ss[0] == 'C') {
192             int k = read(), x = read() ;
193             change_point(root,1,n,bl[bll[k]],x) ;
194         } else if(ss[0] == 'N') {
195             change1() ;
196         } else if(ss[0] == 'S') {
197             query1() ;
198         } else if(ss[1] == 'A') {
199             query2() ;
200         } else query3() ;
201     }
202     return 0 ;
203 }