Tree
http://poj.org/problem?id=3237
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 12268 | Accepted: 3159 |
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
1 3
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
这题的延迟标记是进行取反操作，不是按位取反。。。
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#define maxn 200005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std; struct Tree{;
int Max,Min;
}tree[maxn<<];
int lazy[maxn<<];
int n;
int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
int co,head[maxn];
struct Edge {
int to, next;
}edge[maxn]; void Swap(int &x,int &y){
int t=x;x=-y;y=-t;
} void addedge(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
struct sair{
int x,y,len;
}p[maxn]; void pushdown(int rt){
if(lazy[rt]){
/* tree[rt<<1].Max+=1;
tree[rt<<1|1].Max+=1;
tree[rt<<1].Min+=1;
tree[rt<<1|1].Min+=1;*/
Swap(tree[rt<<].Max,tree[rt<<].Min);
Swap(tree[rt<<|].Max,tree[rt<<|].Min);
lazy[rt<<]^=;
lazy[rt<<|]^=;
lazy[rt]=;
}
} void pushup(int rt){
tree[rt].Max=max(tree[rt<<].Max,tree[rt<<|].Max);
tree[rt].Min=min(tree[rt<<].Min,tree[rt<<|].Min);
} void build(int l,int r,int rt){
lazy[rt]=;
if(l==r){
tree[rt].Max=tree[rt].Min=;
return;
}
int mid=(l+r)/;
build(lson);
build(rson);
pushup(rt);
} void add(int L,int R,int k,int l,int r,int rt){
if(L<=l&&R>=r){
tree[rt].Max=tree[rt].Min=k;
return;
}
pushdown(rt);
int mid=(l+r)/;
if(L<=mid) add(L,R,k,lson);
if(R>mid) add(L,R,k,rson);
pushup(rt);
} void nega(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r){
Swap(tree[rt].Max,tree[rt].Min);
lazy[rt]^=;
return;
}
pushdown(rt);
int mid=(l+r)/;
if(L<=mid) nega(L,R,lson);
if(R>mid) nega(L,R,rson);
pushup(rt);
} int query(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r){
return tree[rt].Max;
}
pushdown(rt);
int mid=(l+r)/;
int ans=-0x3f3f3f3f;
if(L<=mid) ans=max(ans,query(L,R,lson));
if(R>mid) ans=max(ans,query(L,R,rson));
pushup(rt);
return ans;
} void dfs1(int now,int f,int deep){
dep[now]=deep;
siz[now]=;
fa[now]=f;
int maxson=-;
for(int i=head[now];~i;i=edge[i].next){
if(edge[i].to != fa[now]) {
dfs1(edge[i].to,now,deep+);
siz[now]+=siz[edge[i].to];
if(siz[edge[i].to]>maxson){
maxson=siz[edge[i].to];
son[now]=edge[i].to;
}
}
}
} void dfs2(int now,int topp){
id[now]=++cnt;
top[now]=topp;
if(!son[now]) return;
dfs2(son[now],topp);
for(int i=head[now];~i;i=edge[i].next){
int vvv = edge[i].to;
if(vvv==son[now]||vvv==fa[now]) continue;
dfs2(vvv,vvv);
}
} int qRange(int x,int y){
int t1 = top[x], t2 = top[y];
int res = -0x3f3f3f3f;
while(t1 != t2) {
if(dep[t1] < dep[t2]) {
swap(t1, t2); swap(x, y);
}
res = max(res,query(id[t1], id[x], , n, ));
x = fa[t1]; t1 = top[x];
}
if(x == y) return res;
if(dep[x] > dep[y]) swap(x, y);
return max(res,query(id[son[x]], id[y], , n, ));
} void NRange(int x,int y){
int t1 = top[x], t2 = top[y];
while(t1 != t2) {
if(dep[t1] < dep[t2]) {
swap(t1, t2); swap(x, y);
}
nega(id[t1],id[x],,n,);
x = fa[t1]; t1 = top[x];
}
if(x == y) return;
if(dep[x] > dep[y]) swap(x, y);
nega(id[son[x]],id[y],,n,);
} void addRange(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(id[top[x]],id[x],k,,n,);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
add(id[x],id[y],k,,n,);
} int main(){
int m,r;
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(head, -, sizeof head);
mem(dep,);
mem(fa,);
mem(siz,);
mem(son,);
mem(id,);
mem(top,);
int z,x,y;
co=;
cnt=;
for(int i=;i<n;i++){
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].len);
addedge(p[i].x,p[i].y);
addedge(p[i].y,p[i].x);
}
cnt=;
int xx;
dfs1(,,);
dfs2(,);
build(,n,);
for(int i=;i<n;i++){
if(dep[p[i].x]<dep[p[i].y]) xx=p[i].y;
else xx=p[i].x;
addRange(xx,xx,p[i].len);
}
char pos[];
while(~scanf("%s",pos)){
if(pos[]=='D') break;
scanf("%d %d",&x,&y);
if(pos[]=='C'){
p[x].len=y;
if(dep[p[x].x]<dep[p[x].y]) xx=p[x].y;
else xx=p[x].x;
addRange(xx,xx,p[x].len);
}
else if(pos[]=='N'){
NRange(x,y);
}
else if(pos[]=='Q'){
printf("%d\n",qRange(x,y));
}
}
}
}