月下“毛景树”

题目描述

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。

爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：

• Change k w：将第k条树枝上毛毛果的个数改变为w个。

• Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。

• Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：

• Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

输入输出格式

输入格式：

第一行一个正整数N。

接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。

 

输出格式：

对于毛毛虫的每个询问操作，输出一个答案。

 

输入输出样例

输入样例#1： 

41 2 81 3 73 4 9Max 2 4Cover 2 4 5Add 1 4 10Change 1 16Max 2 4Stop

输出样例#1： 

916

说明

1<=N<=100,000，操作+询问数目不超过100,000。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

 

裸的树链剖分，要注意的点就是覆盖的优先级比加法的大，重点就是pushdown函数

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              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
             
              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
              
               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
               
                 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
                
                 >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
                 
                  >pos){190 if(pos=="Stop") break;191 cin>>x>>y;192 if(pos=="Max"){193 cout<
                  
                   <
                   
                    >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]