poj3237 Tree 树链剖分

本文主要是介绍poj3237 Tree 树链剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：在spoj375基础上增加了一条路径的取反操作，其他都一样。

思路：剖分没有变化，在线段树部分，需要一个tag标记该段是否需要需要取反，记录一个最大值、最小值即可。=  =（打tag的那

段应该已经跟新好，push_down的时候如果tag=1那么直接对两个子段进行更新。。一开始意识模糊了。。）详见代码：

/*********************************************************file name: poj3237.cppauthor : kereocreate time:  2015年01月21日 星期三 10时15分39秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=50;
const int MAXN=10000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,edge_cnt,cnt;
char str[N];
int head[MAXN],sz[MAXN],dep[MAXN],son[MAXN],fa[MAXN],top[MAXN],pos[MAXN];
struct Edge{int u,v,w,next;
}edge[MAXN<<1];
struct node{int l,r;int tag,Min,Max;
}segtree[MAXN<<2];
void init(){edge_cnt=cnt=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w){edge[edge_cnt].u=u; edge[edge_cnt].v=v;edge[edge_cnt].w=w; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
}
void dfs1(int u,int pre,int depth){sz[u]=1; son[u]=0; dep[u]=depth; fa[u]=pre;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v == pre)continue;dfs1(v,u,depth+1);sz[u]+=sz[v];if(sz[son[u]]<sz[v])son[u]=v;}
}
void dfs2(int u,int tp){pos[u]=cnt++; top[u]=tp;if(son[u]!=0)dfs2(son[u],top[u]);for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v == fa[u] || v == son[u])continue;dfs2(v,v);}
}
void build(int rt,int l,int r){segtree[rt].l=l; segtree[rt].r=r;segtree[rt].tag=0; segtree[rt].Min=inf; segtree[rt].Max=-inf;if(l == r)return ;int mid=(l+r)>>1;build(L(rt),l,mid); build(R(rt),mid+1,r);
}
void push_down(int rt){if(segtree[rt].l == segtree[rt].r)return ;if(segtree[rt].tag){segtree[rt].tag=0;segtree[L(rt)].tag^=1; segtree[R(rt)].tag^=1;swap(segtree[L(rt)].Max,segtree[L(rt)].Min);segtree[L(rt)].Max*=-1; segtree[L(rt)].Min*=-1;swap(segtree[R(rt)].Max,segtree[R(rt)].Min);segtree[R(rt)].Max*=-1; segtree[R(rt)].Min*=-1;}
}
void push_up(int rt){segtree[rt].Max=max(segtree[L(rt)].Max,segtree[R(rt)].Max);segtree[rt].Min=min(segtree[L(rt)].Min,segtree[R(rt)].Min);
}
void update(int rt,int p,int x){if(segtree[rt].l == segtree[rt].r){segtree[rt].tag=0;segtree[rt].Max=segtree[rt].Min=x;return ;}push_down(rt);int mid=(segtree[rt].l+segtree[rt].r)>>1;if(p<=mid)update(L(rt),p,x);else update(R(rt),p,x);push_up(rt);
}
void Negate(int rt,int l,int r){if(segtree[rt].l == l && segtree[rt].r == r){segtree[rt].tag^=1;swap(segtree[rt].Max,segtree[rt].Min);segtree[rt].Min*=-1; segtree[rt].Max*=-1;return ;}push_down(rt);int mid=(segtree[rt].l+segtree[rt].r)>>1;if(r<=mid)Negate(L(rt),l,r);else if(l>mid)Negate(R(rt),l,r);else{Negate(L(rt),l,mid); Negate(R(rt),mid+1,r);}push_up(rt);
}
int query(int rt,int l,int r){if(segtree[rt].l ==l &&  segtree[rt].r == r)return segtree[rt].Max;push_down(rt);int mid=(segtree[rt].l+segtree[rt].r)>>1;if(r<=mid)return query(L(rt),l,r);else if(l>mid)return query(R(rt),l,r);elsereturn max(query(L(rt),l,mid),query(R(rt),mid+1,r));push_up(rt);
}
int solve(int id,int u,int v){int ans=-inf;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);if(id == 1)ans=max(ans,query(1,pos[top[u]],pos[u]));else Negate(1,pos[top[u]],pos[u]);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);if(u!=v){if(id == 1)ans=max(ans,query(1,pos[u]+1,pos[v]));else Negate(1,pos[u]+1,pos[v]);}return ans;
}
int main(){int T;scanf("%d",&T);while(T--){init();scanf("%d",&n);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w); addedge(v,u,w);}dfs1(1,1,1); dfs2(1,1); build(1,1,n-1);for(int i=0;i<edge_cnt;i+=2){int u=edge[i].u,v=edge[i].v,w=edge[i].w;if(dep[u]<dep[v])swap(u,v);update(1,pos[u],w);}while(1){scanf("%s",str);if(str[0] == 'D')break;if(str[0] == 'C'){int x,w;scanf("%d%d",&x,&w);x=(x-1)*2;int u=edge[x].u,v=edge[x].v;if(dep[u]<dep[v])swap(u,v);update(1,pos[u],w);}if(str[0] == 'Q'){int u,v;scanf("%d%d",&u,&v);printf("%d\n",solve(1,u,v));}if(str[0] == 'N'){int u,v;scanf("%d%d",&u,&v);solve(2,u,v);}}}return 0;
}

这篇关于poj3237 Tree 树链剖分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---