poj 3237 Tree 题解(树链剖分，线段树)

原题链接： poj

题意简述

多组数据。给定一个树，带边权，要支持三种操作，分别是：

两个节点之间的路径的边权全部$\times -1$，即取相反数单边修改边权值求两个节点之间路径上的最长边

数据

输入

第一行一个$t$，表示有$t$组数据。对于每一个数据，先有一个$n$，表示点数。然后$n-1$行，每行两个数$a,b,c$表示$a,b$之间有一个边，权值为$c$。接下来是一些询问，先有一个字符串，如果是：

“$NEGATE$” 后跟两个数$a,b$，表示$a,b$进行操作$1$“$CHANGE$” 后跟两个数$i,w$，表示将输入的第$i$条边权改为$w$“$QUERY$” 后跟两个数，表示$a,b$进行操作$3$

输出

对于每个操作三（即$QUERY形式给出的操作$），输出答案

样例

输入 1

3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE 输出 1 3

思路

这显然是个树剖。做树剖的题，要先知道一个事情：

这个题放到链上怎么做。

然后用分块打到树上即珂。珂是，这个题放到链上怎么做呢？

part 1. 序列上做法

线段树。显然，维护最大值是好维护的，当然单点修改也能改。关键就是这个取相反数。如果一个区间整个取了相反数，那么你会发现：整个乘了$-1$后，最大值和最小值互换了。 举个栗子：

原区间：$\{1,-10,2,9\}$

最大：9 最小：-10

取相反数：$\{-1,10,2,-9\}$

最大：10 最小：-9

是不是茅塞顿开！（我这个蒟蒻没想到这一点，爆肝调到$11:30p.m.$才搞出来。。。） 所以链上会做了，就是放到树上的问题了。

part 2.放到树上

我们发现，树链剖分都是对点权进行操作的，那么，边权呢？ 会发现，每一个边都连接着一对父子。如果我们把边权，丢到这个边的儿子上，会发现：

每个儿子唯一对应一个边（根除外，根不对应边）

所以，我们就考虑用儿子的点权表示边权。但是注意，在取答案和修改的时候，要做出一些改动。举个栗子：（我们的树长这样） blog1.png 然后我们要对点$3,5$进行查询操作。我们把每个边以（蓝色标出）及对应的点（红色标出）标出来： blog2.jpg 会发现，边是连接了整条路径没错，但是点。。。好像少了一个点。没错，少了$LCA$那个店。那么我们是不是要把$LCA$也打出来呢？ 不不不，别怕，不用。我们只需要在树链剖分的最后一步（即$u$和$v$在同一个链上的单独处理），把原来从$DFSid[u]$到$DFSid[v]$换成$DFSid[son[u]]$到$DFSid[v]$即珂。因为此时我们设$u$是上面（即深度更小）的那个，所以此时$u$就是$LCA$，然后我们只要不取$u$，就完美的解决了这个问题。

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; namespace Flandle_Scarlet { #define N 10100 class Graph//图 { public: int head[N]; int EdgeCount; struct Edge { int To,Label,Next; }Ed[N<<1]; void clear() { memset(Ed,-1,sizeof(Ed)); memset(head,-1,sizeof(head)); EdgeCount=0; } void AddEdge(int u,int v,int w) { ++EdgeCount; Ed[EdgeCount]=(Edge){v,w,head[u]}; head[u]=EdgeCount; } int Start(int u) { return head[u]; } int To(int u) { return Ed[u].To; } int Label(int u) { return Ed[u].Label; } int Next(int u) { return Ed[u].Next; } }G;void Add(int u,int v,int w){G.AddEdge(u,v,w);G.AddEdge(v,u,w);} int n; struct node { int u,v,k; }E[N]; void Input() { scanf("%d",&n); for(int i=1;i<n;++i) { int a,b,k; scanf("%d%d%d",&a,&b,&k); E[i]=(node){a,b,k}; Add(a,b,1); } } int deep[N],size[N],son[N],fa[N]; void DFS1(int u,int f) { deep[u]=deep[f]+1; size[u]=1; fa[u]=f; if (G.Start(u)==-1) return; son[u]=-1;int Max=-1; for(int i=G.Start(u);~i;i=G.Next(i)) { int v=G.To(i); if (v!=f and ~v) { DFS1(v,u); size[u]+=size[v]; if (size[v]>Max) { Max=size[v]; son[u]=v; } } } } int DFSid[N];int cnt=0; int top[N]; void DFS2(int u,int topu) { DFSid[u]=++cnt; top[u]=topu; if (son[u]==-1) return; DFS2(son[u],topu); for(int i=G.Start(u);~i;i=G.Next(i)) { int v=G.To(i); if (v!=son[u] and v!=fa[u] and ~v) { DFS2(v,v); } } }//两遍DFS，模板 int wt[N]; class SegmentTree { public: struct node { int l,r; int mx,mn,a;//最大和最小都要求 }tree[N<<2]; #define ls index<<1 #define rs index<<1|1 #define L tree[index].l #define R tree[index].r #define Mx tree[index].mx #define Mn tree[index].mn #define A tree[index].a #define lL tree[ls].l #define lR tree[ls].r #define lMx tree[ls].mx #define lMn tree[ls].mn #define lA tree[ls].a #define rL tree[rs].l #define rR tree[rs].r #define rMx tree[rs].mx #define rMn tree[rs].mn #define rA tree[rs].a void Update(int index) { Mx=max(lMx,rMx); Mn=min(lMn,rMn); } void BuildTree(int l,int r,int index) { L=l,R=r,Mx=Mn=0,A=1; if (l==r) { Mx=Mn=wt[l]; return; } int mid=(l+r)>>1; BuildTree(l,mid,ls); BuildTree(mid+1,r,rs); Update(index); } void AddOne(int index) { A*=-1; Mx*=-1; Mn*=-1; swap(Mx,Mn);//注意这里不能忘了swap } void PushDown(int index) { if (A!=1) { AddOne(ls); AddOne(rs); A=1; } } void Change(int pos,int x,int index) { if (pos<L or pos>R) return; if (L==R) return (void)(Mx=Mn=x); PushDown(index);//虽然是单点，但也要pushdown（自己理解一下哈） Change(pos,x,ls); Change(pos,x,rs); Update(index); } void Add(int l,int r,int index) { if (l>R or L>r or l>r) return; if (l<=L and R<=r) return AddOne(index); PushDown(index); Add(l,r,ls); Add(l,r,rs); Update(index); } int Query(int l,int r,int index) { if (l>R or L>r or l>r) return -0x3f3f3f3f; if (l<=L and R<=r) return Mx; PushDown(index); return max(Query(l,r,ls),Query(l,r,rs)); } }T; void Build() { DFS1(1,-1); DFS2(1,1); for(int i=1;i<n;++i) { int u=E[i].u,v=E[i].v,w=E[i].k; if (deep[u]>deep[v]) swap(E[i].u,E[i].v),swap(u,v); //这里把每一个边都令u是v的父亲 wt[DFSid[v]]=w; //然后用对应关系处理好边的权值 } T.BuildTree(1,n,1);//不要忘了建树 } void PathNega(int u,int v) { while(top[u]!=top[v]) { if (deep[top[u]]<deep[top[v]]) swap(u,v); T.Add(DFSid[top[u]],DFSid[u],1); u=fa[top[u]]; } if (deep[u]>deep[v]) swap(u,v); if (u!=v)//这个一定要判 T.Add(DFSid[son[u]]/*记得不能取到u*/,DFSid[v],1); } void SingleChange(int u,int x) { T.Change(DFSid[u],x,1); } int PathQuery(int u,int v) { int ans=-0x3f3f3f3f; while(top[u]!=top[v]) { if (deep[top[u]]<deep[top[v]]) swap(u,v); ans=max(ans,T.Query(DFSid[top[u]],DFSid[u],1)); u=fa[top[u]]; } if (deep[u]>deep[v]) swap(u,v); if (u!=v)//同理 ans=max(ans,T.Query(DFSid[son[u]],DFSid[v],1)); return ans; } void Query() { while(1) { char s[10];scanf("%s",s); if (s[0]=='N') { int u,v; scanf("%d%d",&u,&v); PathNega(u,v); } if (s[0]=='C') { int i,w; scanf("%d%d",&i,&w); SingleChange(E[i].v,w); } if (s[0]=='Q') { int u,v; scanf("%d%d",&u,&v); printf("%d\n",PathQuery(u,v)); } if (s[0]=='D') break;//这个不写。。。233我也不说什么了 } } void InitAll()//为了解决poj的毒瘤多组数据 { //variables n=0; cnt=0; //arrays //deep[N],size[N],son[N],fa[N] //DFSid[N] //top[N] //wt[N] memset(deep,0,sizeof(deep)); memset(size,0,sizeof(size)); memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(DFSid,0,sizeof(DFSid)); memset(top,0,sizeof(top)); memset(wt,0,sizeof(wt)); //classes & structs G.clear(); memset(E,0,sizeof(E)); } void Main() { if (0) { freopen("","r",stdin); freopen("ans.txt","w",stdout); //本地调试用的 } int t;scanf("%d",&t); while(t--) { InitAll(); Input(); Build(); Query(); } } }; int main() { Flandle_Scarlet::Main(); return 0; }

回到总题解界面