1583. [POJ3237]树的维护
http://www.cogs.pro/cogs/problem/problem.php?pid=1583
★★★☆ 输入文件：maintaintree.in 输出文件：maintaintree.out 简单对比
时间限制：5 s 内存限制：128 MB
【题目描述】
给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：
CHANGE i v：将第i条边的权值改成v。
NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。
QUERY a b：找出点a到点b路径上各边的最大权值。
【输入格式】
输入文件的第一行有一个整数N（N<=10000）。
接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。
接下来是若干条指令（不超过10^5条），都按照上面所说的格式。
输入文件的最后一行是"DONE".
【输出格式】
对每个“QUERY”指令，输出一行，即路径上各边的最大权值。
【样例输入】
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【样例输出】
1
3
【提示】
这里的输入输出格式和POJ上原题略有不同。
【来源】
难点在于取相反数操作
记录下最大值和最小值，有取相反数操作时，就把两个值变成相反数，再交换两数的值就ok，然后给这个区间打上标记（线段树的lazy标记），以后访问或更改值时记得下传标记就好。
#include <stdio.h> #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 100010; struct Edge{ int to,next; }edge[MAXN*2]; int head[MAXN],tot; int top[MAXN];//top[v]表示v所在的重链的顶端节点 int fa[MAXN]; //父亲节点 int deep[MAXN];//深度 int num[MAXN];//num[v]表示以v为根的子树的节点数 int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置 int fp[MAXN];//和p数组相反 int son[MAXN];//重儿子 int pos; void init(){ tot = 0; memset(head,-1,sizeof(head)); pos = 0; memset(son,-1,sizeof(son)); } void addedge(int u,int v){ edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void dfs1(int u,int v,int d){ deep[v]=d; fa[v]=u; num[v]=1; for(int i=head[v];i!=-1;i=edge[i].next){ int to=edge[i].to; if(to==u)continue; dfs1(v,to,d+1); num[v]+=num[to]; if(son[v]==-1||num[son[v]]<num[to])son[v]=to; } } void dfs2(int u,int v){ top[u]=v; p[u]=pos++; if(son[u]==-1)return; dfs2(son[u],v); for(int i=head[u];i!=-1;i=edge[i].next){ int to=edge[i].to; if(to==fa[u]||to==son[u])continue; dfs2(to,to); } } //线段树 struct Node{ int l,r; int Max; int Min; int ne; }tr[MAXN*3]; void build(int i,int l,int r){ tr[i].l = l; tr[i].r = r; tr[i].Max = 0; tr[i].Min = 0; tr[i].ne = 0; if(l == r)return; int mid = (l+r)/2; build(i<<1,l,mid); build((i<<1)|1,mid+1,r); } void push_up(int i) { tr[i].Max = max(tr[i<<1].Max,tr[(i<<1)|1].Max); tr[i].Min = min(tr[i<<1].Min,tr[(i<<1)|1].Min); } void push_down(int i){ if(tr[i].l == tr[i].r)return; if(tr[i].ne) { tr[i<<1].Max = -tr[i<<1].Max; tr[i<<1].Min = -tr[i<<1].Min; swap(tr[i<<1].Min,tr[i<<1].Max); tr[(i<<1)|1].Max = -tr[(i<<1)|1].Max; tr[(i<<1)|1].Min = -tr[(i<<1)|1].Min; swap(tr[(i<<1)|1].Max,tr[(i<<1)|1].Min); tr[i<<1].ne ^= 1; tr[(i<<1)|1].ne ^= 1; tr[i].ne = 0; } } void update(int i,int k,int val){ // 更新线段树的第k个值为val if(tr[i].l == k && tr[i].r == k) { tr[i].Max = val; tr[i].Min = val; tr[i].ne = 0; return; } push_down(i); int mid = (tr[i].l + tr[i].r)/2; if(k <= mid)update(i<<1,k,val); else update((i<<1)|1,k,val); push_up(i); } void ne_update(int i,int l,int r){ if(tr[i].l==l&&tr[i].r==r){ tr[i].Max=-tr[i].Max;tr[i].Min=-tr[i].Min; swap(tr[i].Max,tr[i].Min); tr[i].ne^=1;return; } push_down(i); int mid=(tr[i].l+tr[i].r)>>1; if(r<=mid)ne_update(i<<1,l,r); else if(l>mid)ne_update((i<<1)|1,l,r); else ne_update(i<<1,l,mid),ne_update((i<<1)|1,mid+1,r); tr[i].Min=min(tr[i<<1].Min,tr[(i<<1)|1].Min); tr[i].Max=max(tr[i<<1].Max,tr[(i<<1)|1].Max); } int query(int i,int l,int r){ //查询线段树中[l,r] 的最大值 if(tr[i].l == l && tr[i].r == r) return tr[i].Max; push_down(i); int mid = (tr[i].l + tr[i].r)/2; if(r <= mid)return query(i<<1,l,r); else if(l > mid)return query((i<<1)|1,l,r); else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r)); push_up(i); } int findmax(int u,int v){//查询u->v边的最大值 int f1 = top[u], f2 = top[v]; int tmp = -100000000; while(f1 != f2) { if(deep[f1] < deep[f2]) { swap(f1,f2); swap(u,v); } tmp = max(tmp,query(1,p[f1],p[u])); u = fa[f1]; f1 = top[u]; } if(u == v)return tmp; if(deep[u] > deep[v]) swap(u,v); return max(tmp,query(1,p[son[u]],p[v])); } void Negate(int u,int v){ int f1=top[u],f2=top[v]; while(f1!=f2){ if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v); ne_update(1,p[f1],p[u]); u=fa[f1];f1=top[u]; } if(u==v)return; if(deep[u]>deep[v])swap(u,v); ne_update(1,p[son[u]],p[v]); return; } int E[MAXN][3]; int main() { //freopen("Cola.txt","r",stdin); freopen("maintaintree.in","r",stdin); freopen("maintaintree.out","w",stdout); int T,n; T=1; while(T--){ init(); scanf("%d",&n); for(int i=0;i<n-1;i++){ scanf("%d%d%d",&E[i][0],&E[i][1],&E[i][2]); addedge(E[i][0],E[i][1]); addedge(E[i][1],E[i][0]); } dfs1(0,1,0); dfs2(1,1); build(1,0,pos-1); for(int i=0;i<n-1;i++){ if(deep[E[i][0]]>deep[E[i][1]])swap(E[i][0],E[i][1]); update(1,p[E[i][1]],E[i][2]); } char ch[10]; int u,v; while(1){ scanf("%s",ch); if(ch[0]=='D')break; scanf("%d%d",&u,&v); if(ch[0]=='Q')printf("%d ",findmax(u,v)); else if(ch[0]=='C')update(1,p[E[u-1][1]],v); else Negate(u,v); } } return 0; }