Tree

Time Limit:?5000MS	?	Memory Limit:?131072K
Total Submissions:?12247	?	Accepted:?3151

Description

You are given a tree with?N?nodes. The tree’s nodes are numbered 1 through?N?and its edges are numbered 1 through?N?? 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

CHANGE?i?v	Change the weight of the?ith edge to?v
NEGATE?a?b	Negate the weight of every edge on the path from?a?to?b
QUERY?a?b	Find the maximum weight of edges on the path from?a?to?b

Input

The input contains multiple test cases. The first line of input contains an integer?t?(t?≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains?N?(N?≤ 10,000). The next?N?? 1 lines each contains three integers?a,?b?and c, describing an edge connecting nodes?a?and?b?with weight?c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

13 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE

Sample Output

1 3

Source

POJ Monthly--2007.06.03, Lei, Tao

題意就是：?有T組數(shù)據(jù) ，給你n個(gè)點(diǎn)的樹，有三種操作：

?1.CHANGE i v :將第i條邊的值改為v? ?

?2.NEGATE a b :將a點(diǎn)到b點(diǎn)路徑上的邊權(quán)取反? ? ??

3.QUERY a b :查詢a點(diǎn)到b點(diǎn)路徑上最大的邊權(quán)值，

?

由于有取反操作，記錄最大和最小值 然后取反并交換就可以，用線段樹來(lái)維護(hù)，真香警告。。。

?

代碼:

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<bitset> 6 #include<cassert> 7 #include<cctype> 8 #include<cmath> 9 #include<cstdlib> 10 #include<ctime> 11 #include<deque> 12 #include<iomanip> 13 #include<list> 14 #include<map> 15 #include<queue> 16 #include<set> 17 #include<stack> 18 #include<vector> 19 using namespace std; 20 typedef long long ll; 21 22 const double PI=acos(-1.0); 23 const double eps=1e-6; 24 const ll mod=1e9+7; 25 const int inf=0x3f3f3f3f; 26 const int maxn=1e4+10; 27 const int maxm=100+10; 28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 29 #define lson l,m,rt<<1 30 #define rson m+1,r,rt<<1|1 31 32 int head[maxn],cnt,num,n; 33 34 struct Edge{ 35 int to,next; 36 }edge[maxn<<1]; 37 38 void add(int u,int v)//存圖(樹) 39 { 40 edge[cnt].to=v; 41 edge[cnt].next=head[u]; 42 head[u]=cnt++; 43 } 44 45 int val[maxn],siz[maxn],dep[maxn],son[maxn]; 46 int top[maxn],tid[maxn],pos[maxn],fa[maxn]; 47 48 void init()//初始化 49 { 50 memset(head,-1,sizeof(head)); 51 memset(son,-1,sizeof(son)); 52 cnt=num=0; 53 } 54 55 ///樹鏈剖分部分 56 void dfs1(int u,int father)//第一遍dfs，可以得到當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的深度，當(dāng)前節(jié)點(diǎn)的重兒子 57 { 58 //更新dep，fa，siz數(shù)組 59 siz[u]=1;//保存以u(píng)為根的子樹節(jié)點(diǎn)個(gè)數(shù) 60 fa[u]=father;//保存爸爸 61 dep[u]=dep[father]+1;//記錄深度 62 for(int i=head[u];~i;i=edge[i].next){//遍歷所有和當(dāng)前節(jié)點(diǎn)連接的節(jié)點(diǎn) 63 int v=edge[i].to; 64 if(v!=father){//如果連接的是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)，則不處理 65 dfs1(v,u); 66 siz[u]+=siz[v];//直接子樹節(jié)點(diǎn)相加，當(dāng)前節(jié)點(diǎn)的size加上子節(jié)點(diǎn)的size 67 if(son[u]==-1||siz[v]>siz[son[u]])//如果沒(méi)有設(shè)置過(guò)重節(jié)點(diǎn)son或者子節(jié)點(diǎn)v的size大于之前記錄的重節(jié)點(diǎn)son，進(jìn)行更新 68 son[u]=v;//保存重兒子 69 } 70 } 71 } 72 73 void dfs2(int u,int tp)//將各個(gè)重節(jié)點(diǎn)連接成重鏈，輕節(jié)點(diǎn)連接成輕鏈，并且將重鏈(區(qū)間)用數(shù)據(jù)結(jié)構(gòu)(一般是樹狀數(shù)組或者線段樹)來(lái)維護(hù)，并且為每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，其實(shí)就是dfs在執(zhí)行時(shí)的順序(tid數(shù)組)，以及當(dāng)前節(jié)點(diǎn)所在鏈的起點(diǎn)(top數(shù)組)還有當(dāng)前節(jié)點(diǎn)在樹中的位置(pos) ) 74 { 75 top[u]=tp;//保存當(dāng)前節(jié)點(diǎn)所在的鏈的頂端節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的起點(diǎn) 76 tid[u]=++num;//保存樹中每個(gè)節(jié)點(diǎn)剖分以后的新編號(hào)(dfs的執(zhí)行順序) 77 pos[tid[u]]=u;//保存當(dāng)前節(jié)點(diǎn)在樹中的位置，設(shè)置dfs序號(hào)對(duì)應(yīng)成當(dāng)前節(jié)點(diǎn) 78 if(son[u]==-1) return ;//如果當(dāng)前節(jié)點(diǎn)沒(méi)有處在重鏈上，則不處理 79 dfs2(son[u],tp);//將這條重鏈上的所有節(jié)點(diǎn)都設(shè)置成起始的重節(jié)點(diǎn) 80 for(int i=head[u];~i;i=edge[i].next){//遍歷所有和當(dāng)前節(jié)點(diǎn)連接的節(jié)點(diǎn) 81 int v=edge[i].to;//如果連接節(jié)點(diǎn)不是當(dāng)前節(jié)點(diǎn)的重節(jié)點(diǎn)并且也不是u的父節(jié)點(diǎn)，則將其的top設(shè)置成自己，進(jìn)一步遞歸 82 if(v!=son[u]&&v!=fa[u]) 83 dfs2(v,v); 84 } 85 } 86 87 int lazy[maxn<<2],Max[maxn<<2],Min[maxn<<2]; 88 89 //線段樹部分 90 void Swap(int &x,int &y){int t=x;x=-y;y=-t;} 91 92 void pushup(int rt) 93 { 94 Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); 95 Min[rt]=min(Min[rt<<1],Min[rt<<1|1]); 96 } 97 98 void pushdown(int rt) 99 { 100 if(lazy[rt]){ 101 lazy[rt<<1]+=lazy[rt]; 102 lazy[rt<<1|1]+=lazy[rt]; 103 if(lazy[rt]&1){ //兩個(gè)子區(qū)間是否取反依靠當(dāng)前區(qū)間的懶惰標(biāo)記判斷,判斷奇偶 104 Swap(Max[rt<<1],Min[rt<<1]); 105 Swap(Max[rt<<1|1],Min[rt<<1|1]); 106 } 107 lazy[rt]=0; 108 } 109 } 110 111 void build(int l,int r,int rt) 112 { 113 lazy[rt]=0; 114 if(l==r){ 115 Max[rt]=Min[rt]=0; 116 return ; 117 } 118 119 int m=(l+r)>>1; 120 build(lson); 121 build(rson); 122 pushup(rt); 123 } 124 125 void update(int pos,int val,int l,int r,int rt) 126 { 127 if(l==r&&l==pos){ 128 Max[rt]=val;Min[rt]=val;lazy[rt]=0; 129 return ; 130 } 131 132 pushdown(rt); 133 int m=(l+r)>>1; 134 if(pos<=m) update(pos,val,lson); 135 else update(pos,val,rson); 136 pushup(rt); 137 } 138 139 void Negate(int L,int R,int l,int r,int rt)//Negate是int tmp=Max,Max=-Min,Min=-tmp 140 { 141 if(L<=l&&r<=R){ 142 lazy[rt]++; 143 Swap(Max[rt],Min[rt]);//這里要馬上取反 144 return ; 145 } 146 147 pushdown(rt); 148 int m=(l+r)>>1; 149 if(L<=m) Negate(L,R,lson); 150 if(R> m) Negate(L,R,rson); 151 pushup(rt); 152 } 153 154 int query(int L,int R,int l,int r,int rt) 155 { 156 if(L<=l&&r<=R){ 157 return Max[rt]; 158 } 159 160 pushdown(rt); 161 int ret=-inf; 162 int m=(l+r)>>1; 163 if(L<=m) ret=max(ret,query(L,R,lson)); 164 if(R> m) ret=max(ret,query(L,R,rson)); 165 pushup(rt); 166 return ret; 167 } 168 169 int get_max(int u,int v) 170 { 171 int ans=-1<<30; 172 while(top[u]!=top[v]){ 173 if(dep[top[u]]<dep[top[v]]) swap(u,v); 174 ans=max(ans,query(tid[top[u]],tid[u],1,n,1)); 175 u=fa[top[u]]; 176 } 177 178 if(dep[v]<dep[u]) swap(u,v); 179 ans=max(ans,query(tid[son[u]],tid[v],1,n,1));//這里寫撈了，tid[son[u]],寫成tid[u],wa了好幾天。。。 180 printf("%d\n",ans); 181 } 182 183 void change(int u,int v) 184 { 185 while(top[u]!=top[v]){ 186 if(dep[top[u]]<dep[top[v]]) swap(u,v); 187 Negate(tid[top[u]],tid[u],1,n,1); 188 u=fa[top[u]]; 189 } 190 191 if(u==v) return ; 192 if(dep[v]<dep[u]) swap(u,v); 193 Negate(tid[son[u]],tid[v],1,n,1); 194 } 195 196 struct eg{ 197 int u,v,val; 198 }eg[maxn]; 199 200 int main() 201 { 202 int t; 203 scanf("%d",&t); 204 while(t--){ 205 scanf("%d",&n); 206 init(); 207 for(int i=1;i<n;i++){ 208 scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].val); 209 add(eg[i].u,eg[i].v);//加邊 210 add(eg[i].v,eg[i].u);//加邊 211 } 212 dfs1(1,0);//第一遍dfs 213 dfs2(1,1);//第二遍dfs 214 build(1,n,1); 215 for(int i=1;i<n;i++){ 216 if(dep[eg[i].u]<dep[eg[i].v]) swap(eg[i].u,eg[i].v); 217 update(tid[eg[i].u],eg[i].val,1,n,1); 218 } 219 int a,b; 220 char op[10]; 221 while(scanf("%s",op)&&op[0]!='D'){ 222 scanf("%d%d",&a,&b); 223 if(op[0]=='Q'){ 224 get_max(a,b); 225 } 226 if(op[0]=='C'){ 227 update(tid[eg[a].u],b,1,n,1); 228 } 229 if(op[0]=='N'){ 230 change(a,b); 231 } 232 } 233 } 234 }

?

?

?

?

哈哈哈哈，加油加油。

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZERO-/p/9670796.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3237.Tree -树链剖分(边权)(边值更新、路径边权最值、区间标记)贴个板子备忘...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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