POJ 2763 Housewife Wind (树链剖分+线段树)

题目链接：POJ 2763 Housewife Wind

题意：抽象出来就是 一棵已知节点之间的边权，两个操作，1·修改边权，2·询问两个节点之间的边权和。

AC代码：

#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100000+10;
const int inf=9999999999;
struct Edge{
	int to,next;
};
struct Edge edge[maxn*2];
int head[maxn],tot;
int stree[maxn];//节点v在线段树上的编号
int pre[maxn];//在线段树中编号为v节点所对应原图中的编号。
int fa[maxn];//f[v] 表示v的父亲节点
int son[maxn];//表示 与v同在一重链上的儿子节点（重儿子）
int num[maxn];//num[v] v为根的子树的节点数。
int top[maxn];//top[v] v所在链的顶端节点。
int deep[maxn];//deep[v] 表示v的深度（根的深度为1）
int data[maxn];

int pos,n;

void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}

void dfs1(int u,int father,int dep){
	int i;
	deep[u]=dep;
	fa[u]=father;
	num[u]=1;
	for(i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v!=father){
			dfs1(v,u,dep+1);
			num[u]+=num[v];
			if(son[u]==-1 || num[v]>num[son[u]]){
				son[u]=v;
			}
		}
	}
}
//给点编号得到线段树上的对应标号
void getpos(int u,int sp){
	int i;
	top[u]=sp;
	stree[u]=pos++;
	pre[stree[u]]=u;
	if(son[u]==-1) 
		return ;
	getpos(son[u],sp);
	for(i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v!=son[u] && v!=fa[u]){
			getpos(v,v);
		}
	}
}

//树状数组or线段树or其他

int Max(int a,int b){
	if(a>b) return a;
	return b;
}

struct node{
	int l,r;
	int sum,max;
};
struct node tree[maxn*3];

void PushUp(int rt){
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}

void build(int l,int r,int rt){
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].sum=0;
	if(l==r){
		return ;
	}
	int m=(tree[rt].l+tree[rt].r)>>1;
	build(lson);
	build(rson);
	PushUp(rt);
}

void update(int p,int add,int rt){
	if(tree[rt].l==tree[rt].r && tree[rt].l==p){
		tree[rt].sum=add;
		return ;
	}
	int m=(tree[rt].l+tree[rt].r)>>1;
	if(p<=m) update(p,add,rt<<1);
	else update(p,add,rt<<1|1);
	PushUp(rt);
}

int query_sum(int L,int R,int rt){
	if(L<=tree[rt].l && tree[rt].r<=R){
		return tree[rt].sum;
	}
	int m=(tree[rt].l+tree[rt].r)>>1;
	int ret=0;
	if(L<=m) ret+=query_sum(L,R,rt<<1);
	if(R>m) ret+=query_sum(L,R,rt<<1|1);
	return ret;
}

int find_sum(int u,int v){
	int f1,f2,ans=0;
	f1=top[u];
	f2=top[v];
	while(f1!=f2){
		//始终f1的深度比f2要大。深度大先更新
		if(deep[f1]<deep[f2]){
			swap(f1,f2);
			swap(u,v);
		}
		ans+=query_sum(stree[f1],stree[u],1);
		u=fa[f1];
		f1=top[u];
	}
	if(u==v) return ans; 
	if(deep[u]>deep[v]) 
		swap(u,v);
	ans+=query_sum(stree[son[u]],stree[v],1);
	return ans;
}

void init(){
	tot=0;
	memset(head,-1,sizeof head);
	pos=0;
	memset(son,-1,sizeof son);
}
int e[maxn][5];

int main()
{ 
	int t,x,y;
	int q,i,s,tmp;
	init();
	scanf("%d%d%d",&n,&q,&s);
	tmp=s;
	for(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(1,0,0);//根的deep是0.father从0开始。
	getpos(1,1);
	build(1,n,1);
	for(i=0;i<n-1;i++){
		if(deep[e[i][0]]>deep[e[i][1]]) 
			swap(e[i][0],e[i][1]);
		update(stree[e[i][1]],e[i][2],1);
	}
	int op;
	while(q--){
		int a,b;
		scanf("%d",&op);
		if(op==0){
			scanf("%d",&a);
			printf("%d\n",find_sum(tmp,a));
			tmp=a;
		}
		else{
			scanf("%d %d",&a,&b);
			update(stree[e[a-1][1]],b,1);
		}
	}

	return 0;
}

POJ 2763 Housewife Wind (树链剖分+线段树)

原文：http://blog.csdn.net/u012377575/article/details/43559757