Description 毛毛蟲經(jīng)過及時的變形，最終逃過的一劫，離開了菜媽的菜園。 毛毛蟲經(jīng)過千山萬水，歷盡千辛萬苦，最后來到了小小的紹興一中的校園里。爬啊爬~爬啊爬~~毛毛蟲爬到了一顆小小的“毛景樹”下面，發(fā)現(xiàn)樹上長著他最愛吃的毛毛果~~~ “毛景樹”上有N個節(jié)點和N-1條樹枝，但節(jié)點上是沒有毛毛果的，毛毛果都是長在樹枝上的。但是這棵“毛景樹”有著神奇的魔力，他能改變樹枝上毛毛果的個數(shù)： ? Change k w：將第k條樹枝上毛毛果的個數(shù)改變?yōu)閣個。 ? Cover u v w：將節(jié)點u與節(jié)點v之間的樹枝上毛毛果的個數(shù)都改變?yōu)閣個。 ? Add u v w：將節(jié)點u與節(jié)點v之間的樹枝上毛毛果的個數(shù)都增加w個。 由于毛毛蟲很貪，于是他會有如下詢問： ? Max u v：詢問節(jié)點u與節(jié)點v之間樹枝上毛毛果個數(shù)最多有多少個。 Input 第一行一個正整數(shù)N。 接下來N-1行，每行三個正整數(shù)Ui，Vi和Wi，第i+1行描述第i條樹枝。表示第i條樹枝連接節(jié)點Ui和節(jié)點Vi，樹枝上有Wi個毛毛果。 接下來是操作和詢問，以“Stop”結束。 Output 對于毛毛蟲的每個詢問操作，輸出一個答案。 Sample Input 4 1 2 8 1 3 7 3 4 9 Max 2 4 Cover 2 4 5 Add 1 4 10 Change 1 16 Max 2 4 Stop Sample Output 9 16 【Data Range】 1<=N<=100,000，操作+詢問數(shù)目不超過100,000。 保證在任意時刻，所有樹枝上毛毛果的個數(shù)都不會超過10^9個。 題面

解題思路：邊權化點權，將邊權放到深度較深的點上面

對于操作：
Change k w：將第k條樹枝上毛毛果的個數(shù)改變?yōu)閣個。
=>直接找對應的點，線段樹上單點修改
Cover u v w：將節(jié)點u與節(jié)點v之間的樹枝上毛毛果的個數(shù)都改變?yōu)閣個。
=>注意：u和v的lca是不應該被修改的
為了方便，我們可以先修改，再把lca改回去
Add u v w：將節(jié)點u與節(jié)點v之間的樹枝上毛毛果的個數(shù)都增加w個。
=>注意：u和v的lca是不應該被加的
為了方便，我們可以先修改，再把lca減回去
Max u v：詢問節(jié)點u與節(jié)點v之間樹枝上毛毛果個數(shù)最多有多少個。
=>注意：u和v的lca是不應該被算進去的
我們可以先將lca賦成極小值
得到答案后在將原值賦回去
值得注意的地方是線段樹的標記下放：
先修改操作，后加操作，保證正確性

1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const ll N=1e5+10; 5 struct node{ 6 ll u,v,c,ne; 7 }e[N*2]; 8 ll h[N],tot,n; 9 void add(ll u,ll v,ll c) 10 { 11 tot++;e[tot]=(node){u,v,c,h[u]};h[u]=tot; 12 e[tot+n-1]=(node){v,u,c,h[v]};h[v]=tot+n-1; 13 } 14 ll dep[N],size[N],son[N],f[N]; 15 ll val[N],w[N],id[N],top[N]; 16 ll Max[N*6],ad[N*6],fg[N*6]; 17 void build(ll o,ll l,ll r) 18 { 19 fg[o]=-1;ad[o]=0; 20 if(l==r){ 21 Max[o]=w[l]; 22 return; 23 } 24 ll mid=(l+r)>>1; 25 build(o<<1,l,mid);build(o<<1|1,mid+1,r); 26 Max[o]=max(Max[o<<1],Max[o<<1|1]); 27 } 28 void down(ll o) 29 { 30 if(fg[o]!=-1) 31 { 32 fg[o<<1]=Max[o<<1]=fg[o]; 33 fg[o<<1|1]=Max[o<<1|1]=fg[o]; 34 ad[o<<1]=ad[o<<1|1]=0; 35 fg[o]=-1; 36 } 37 if(ad[o]) 38 { 39 Max[o<<1]+=ad[o];Max[o<<1|1]+=ad[o]; 40 if(fg[o<<1]!=-1) fg[o<<1]+=ad[o]; 41 else ad[o<<1]+=ad[o]; 42 if(fg[o<<1|1]!=-1) fg[o<<1|1]+=ad[o]; 43 else ad[o<<1|1]+=ad[o]; 44 ad[o]=0; 45 } 46 } 47 void tchange(ll o,ll l,ll r,ll x,ll y,ll k) 48 { 49 if(x<=l && y>=r) 50 { 51 Max[o]=k;fg[o]=k;ad[o]=0; 52 return; 53 } 54 down(o); 55 ll mid=(l+r)>>1; 56 if(x<=mid) tchange(o<<1,l,mid,x,y,k); 57 if(y>=mid+1) tchange(o<<1|1,mid+1,r,x,y,k); 58 Max[o]=max(Max[o<<1],Max[o<<1|1]); 59 } 60 void tadd(ll o,ll l,ll r,ll x,ll y,ll k) 61 { 62 if(x<=l && y>=r) 63 { 64 ad[o]+=k;Max[o]+=k; 65 return; 66 } 67 down(o); 68 ll mid=(l+r)>>1; 69 if(x<=mid) tadd(o<<1,l,mid,x,y,k); 70 if(y>=mid+1) tadd(o<<1|1,mid+1,r,x,y,k); 71 Max[o]=max(Max[o<<1],Max[o<<1|1]); 72 } 73 ll tquery(ll o,ll l,ll r,ll x,ll y) 74 { 75 if(x<=l && y>=r) return Max[o]; 76 down(o); 77 ll mid=(l+r)>>1,tmp=-1e9; 78 if(x<=mid) tmp=max(tmp,tquery(o<<1,l,mid,x,y)); 79 if(y>=mid+1) tmp=max(tmp,tquery(o<<1|1,mid+1,r,x,y)); 80 return tmp; 81 } 82 void dfs1(ll u) 83 { 84 size[u]=1;ll p=-1; 85 for(ll i=h[u],rr;i;i=e[i].ne) 86 { 87 rr=e[i].v; 88 if(!dep[rr]) 89 { 90 dep[rr]=dep[u]+1;f[rr]=u;val[rr]=e[i].c; 91 dfs1(rr);size[u]+=size[rr]; 92 if(size[rr]>p) 93 p=size[rr],son[u]=rr; 94 } 95 } 96 } 97 void dfs2(ll u,ll up) 98 { 99 if(u==0) return; 100 id[u]=++tot;w[tot]=val[u]; 101 top[u]=up; 102 dfs2(son[u],up); 103 for(ll i=h[u],rr;i;i=e[i].ne) 104 { 105 rr=e[i].v; 106 if(rr!=f[u] && rr!=son[u]) dfs2(rr,rr); 107 } 108 } 109 void Qchange(ll x,ll y,ll k) 110 { 111 while(top[x]!=top[y]) 112 { 113 if(dep[top[x]]<dep[top[y]]) swap(x,y); 114 tchange(1,1,n,id[top[x]],id[x],k); 115 x=f[top[x]]; 116 } 117 if(dep[x]>dep[y]) swap(x,y); 118 tchange(1,1,n,id[x],id[y],k); 119 } 120 void Qadd(ll x,ll y,ll k) 121 { 122 while(top[x]!=top[y]) 123 { 124 if(dep[top[x]]<dep[top[y]]) swap(x,y); 125 tadd(1,1,n,id[top[x]],id[x],k); 126 x=f[top[x]]; 127 } 128 if(dep[x]>dep[y]) swap(x,y); 129 tadd(1,1,n,id[x],id[y],k); 130 } 131 ll Qmax(ll x,ll y) 132 { 133 ll ans=-1; 134 while(top[x]!=top[y]) 135 { 136 if(dep[top[x]]<dep[top[y]]) swap(x,y); 137 ans=max(ans,tquery(1,1,n,id[top[x]],id[x])); 138 x=f[top[x]]; 139 } 140 if(dep[x]>dep[y]) swap(x,y); 141 ans=max(ans,tquery(1,1,n,id[x],id[y])); 142 return ans; 143 } 144 ll lca(ll x,ll y) 145 { 146 while(top[x]!=top[y]) 147 { 148 if(dep[top[x]]<dep[top[y]]) swap(x,y); 149 x=f[top[x]]; 150 } 151 if(dep[x]>dep[y]) swap(x,y); 152 return x; 153 } 154 char op[10]; 155 ll x,y,z,fa,tmp; 156 int main() 157 { 158 scanf("%lld",&n); 159 for(ll i=1;i<=n-1;++i) 160 { 161 scanf("%lld%lld%lld",&x,&y,&z); 162 add(x,y,z); 163 } 164 dep[1]=1;dfs1(1); 165 val[1]=-1e9;tot=0;dfs2(1,1); 166 build(1,1,n); 167 while(scanf("%s",op)!=EOF) 168 { 169 if(op[1]=='t') break; 170 if(op[1]=='h')//將第x條樹枝上毛毛果的個數(shù)改變?yōu)閥個 171 { 172 scanf("%lld%lld",&x,&y); 173 x=(dep[e[x].u]>dep[e[x].v] ? e[x].u:e[x].v); 174 tchange(1,1,n,id[x],id[x],y); 175 } 176 if(op[1]=='o')//將節(jié)點x與節(jié)點y之間的都改變?yōu)閦個 177 { 178 scanf("%lld%lld%lld",&x,&y,&z); 179 fa=lca(x,y);tmp=tquery(1,1,n,id[fa],id[fa]); 180 Qchange(x,y,z);tchange(1,1,n,id[fa],id[fa],tmp); 181 } 182 if(op[1]=='d')//將節(jié)點x與節(jié)點y之間的都增加z個 183 { 184 scanf("%lld%lld%lld",&x,&y,&z); 185 fa=lca(x,y); 186 Qadd(x,y,z);tadd(1,1,n,id[fa],id[fa],-z); 187 } 188 if(op[1]=='a')//詢問節(jié)點x與節(jié)點y之間最多有多少個 189 { 190 scanf("%lld%lld",&x,&y); 191 fa=lca(x,y);tmp=tquery(1,1,n,id[fa],id[fa]); 192 tchange(1,1,n,id[fa],id[fa],-1e9); 193 printf("%lld\n",Qmax(x,y)); 194 tchange(1,1,n,id[fa],id[fa],tmp); 195 } 196 } 197 return 0; 198 } 代碼

轉載于:https://www.cnblogs.com/adelalove/p/8709620.html

總結

以上是生活随笔為你收集整理的月下“毛景树”的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。