月下“毛景树”

  1 #include<iostream>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<cstdio>
  6 #include<algorithm>
  7 #include<vector>
  8 #define maxn 100005
  9 #define lson l,mid,rt<<1
 10 #define rson mid+1,r,rt<<1|1
 11 using namespace std;
 12 
 13 int tree[maxn<<3],Add[maxn<<3],Change[maxn<<3];
 14 int n;
 15 int v[maxn],val[maxn];
 16 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
 17 vector<int>ve[maxn];
 18 struct sair{
 19     int x,y,len;
 20 }p[maxn];
 21 
 22 void pushup(int rt){
 23     tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
 24 }
 25 
 26 void pushdown(int rt){
 27     if(Change[rt]!=-1){
 28         Change[rt<<1]=Change[rt<<1|1]=Change[rt];
 29         Add[rt<<1]=Add[rt<<1|1]=0;
 30         tree[rt<<1]=tree[rt<<1|1]=Change[rt];
 31     }
 32     if(Add[rt]){
 33         Add[rt<<1]+=Add[rt];
 34         Add[rt<<1|1]+=Add[rt];
 35         tree[rt<<1]+=Add[rt];
 36         tree[rt<<1|1]+=Add[rt];
 37     }
 38     Change[rt]=-1;
 39     Add[rt]=0;
 40 }
 41 
 42 void build(int l,int r,int rt){
 43     Add[rt]=0;
 44     Change[rt]=-1;
 45     if(l==r){
 46         tree[rt]=val[l];
 47         return;
 48     }
 49     int mid=(l+r)/2;
 50     build(lson);
 51     build(rson);
 52     pushup(rt);
 53 }
 54 
 55 void add(int L,int R,int k,int l,int r,int rt){
 56     if(L<=l&&R>=r){
 57         tree[rt]+=k;
 58         Add[rt]+=k;
 59         pushdown(rt);
 60         return;
 61     }
 62     int mid=(l+r)/2;
 63     pushdown(rt);
 64     if(L<=mid) add(L,R,k,lson);
 65     if(R>mid) add(L,R,k,rson);
 66     pushup(rt);
 67 }
 68 
 69 void change(int L,int R,int k,int l,int r,int rt){
 70     if(L<=l&&R>=r){
 71         tree[rt]=k;
 72         Add[rt]=0;
 73         Change[rt]=k;
 74         pushdown(rt);
 75         return;
 76     }
 77     int mid=(l+r)/2;
 78     pushdown(rt);
 79     if(L<=mid) change(L,R,k,lson);
 80     if(R>mid) change(L,R,k,rson);
 81     pushup(rt);
 82 }
 83 
 84 int query(int L,int R,int l,int r,int rt){
 85     if(L<=l&&R>=r){
 86         return tree[rt];
 87     }
 88     int mid=(l+r)/2;
 89     pushdown(rt);
 90     int ans=0;
 91     if(L<=mid) ans=max(ans,query(L,R,lson));
 92     if(R>mid) ans=max(ans,query(L,R,rson));
 93     pushup(rt);
 94     return ans;
 95 }
 96 
 97 void dfs1(int now,int f,int deep){
 98     dep[now]=deep;
 99     siz[now]=1;
100     fa[now]=f;
101     int maxson=-1;
102     for(int i=0;i<ve[now].size();i++){
103         if(ve[now][i]==f) continue;
104         dfs1(ve[now][i],now,deep+1);
105         siz[now]+=siz[ve[now][i]];
106         if(siz[ve[now][i]]>maxson){
107             maxson=siz[ve[now][i]];
108             son[now]=ve[now][i];
109         }
110     }
111 }
112 
113 void dfs2(int now,int topp){
114     id[now]=++cnt;
115     val[cnt]=v[now];
116     top[now]=topp;
117     if(!son[now]) return;
118     dfs2(son[now],topp);
119     for(int i=0;i<ve[now].size();i++){
120         if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue;
121         dfs2(ve[now][i],ve[now][i]);
122     }
123 }
124 
125 int qRange(int x,int y){
126     int t1 = top[x], t2 = top[y];
127     int res = 0;
128     while(t1 != t2) {
129         if(dep[t1] < dep[t2]) {
130             swap(t1, t2); swap(x, y);
131         }
132         res = max(res,query(id[t1], id[x], 1, n, 1));
133         x = fa[t1]; t1 = top[x];
134     }
135     if(x == y) return res;
136     if(dep[x] > dep[y]) swap(x, y);
137     return max(res,query(id[son[x]], id[y], 1, n, 1));
138 }
139 
140 void addRange(int x,int y,int k){
141     int t1 = top[x], t2 = top[y];
142     while(t1 != t2) {
143         if(dep[t1] < dep[t2]) {
144             swap(t1, t2); swap(x, y);
145         }
146         add(id[t1], id[x], k, 1, n, 1);
147         x = fa[t1]; t1 = top[x];
148     }
149     if(x == y) return ;
150     if(dep[x] > dep[y]) swap(x, y);
151     add(id[son[x]], id[y], k, 1, n, 1);
152 }
153 
154 void changeRange(int x,int y,int k){
155     int t1 = top[x], t2 = top[y];
156     while(t1 != t2) {
157         if(dep[t1] < dep[t2]) {
158             swap(t1, t2); swap(x, y);
159         }
160         change(id[t1], id[x], k, 1, n, 1);
161         x = fa[t1]; t1 = top[x];
162     }
163     if(x == y) return ;
164     if(dep[x] > dep[y]) swap(x, y);
165     change(id[son[x]], id[y], k, 1, n, 1);
166 }
167 
168 int main(){
169     std::ios::sync_with_stdio(false);
170     int m,r;
171     cin>>n;
172     for(int i=1;i<n;i++){
173         cin>>p[i].x>>p[i].y>>p[i].len;
174         ve[p[i].x].push_back(p[i].y);
175         ve[p[i].y].push_back(p[i].x);
176     }
177     int z,x,y;
178     string pos;
179     cnt=0;
180     dfs1(1,0,1);
181     dfs2(1,1);
182     build(1,n,1);
183     int xx;
184     for(int i=1;i<n;i++){
185         if(dep[p[i].x]<dep[p[i].y]) xx=p[i].y;
186         else xx=p[i].x;
187         change(id[xx],id[xx],p[i].len,1,n,1);
188     }
189     while(cin>>pos){
190         if(pos=="Stop") break;
191         cin>>x>>y;
192         if(pos=="Max"){
193            cout<<qRange(x,y)<<endl;
194         }
195         else if(pos=="Cover"){
196             cin>>z;
197             changeRange(x,y,z);
198         }
199         else if(pos=="Add"){
200             cin>>z;
201             addRange(x,y,z);
202         }
203         else if(pos=="Change"){
204             if(dep[p[x].x]<dep[p[x].y]) xx=p[x].y;
205             else xx=p[x].x;
206             change(id[xx],id[xx],y,1,n,1);
207             p[x].len=y;
208         }
209     }
210 }
211 /*
212 7
213 1 2 1
214 1 3 2
215 2 4 3
216 2 5 4
217 3 7 6
218 5 6 5
219 Max 1 6
220 */