Home > OI > poj 2763

poj 2763


这题要求两个操作:求树上两个顶点的距离,以及改变某条边的权值。

通过巧妙地利用DFS序列和树状数组,我们可以在O(lg n)时间内完成每个操作。

比如对于一个有8个顶点,且边集如下的树:

1 2

1 3

1 4

2 5

2 6

4 7

7 8

它的DFS序列为 1 2 5 6 3 4 7 8

对于某条树上的边,我们将边指向的子结点的权值加上边的权值,再将这棵子树之后的第一个结点的权值减去这条边的权值,那么就可以用一个树状数组维护每个结点到根结点的距离。

比如 连接1和2的这条边权值为3,我们在2上加3,在3上减3即可。这样修改边权也非常方便。

两个结点间距离:dis(a)+dis(b)-2*dis(LCA(Tree,a,b))

拿这题来复习树状数组,RMQ,LCA…

要注意几个情况

RE一般是数组没开够 开大点..

TLE可能是算法没优化好 实在不行试试用getchar输入加速

WA原因很多,要注意结点到自身的LCA

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 222222
struct Edge{
	int v,w;
	Edge *next;
} *edge[MAXN], mempool[MAXN];
int memnum, road[MAXN][3], dep[MAXN], vis[MAXN], tapp[MAXN],
stack[MAXN], app[MAXN], snum, tnum, n, q, cur, tree[MAXN],
son[MAXN], cnum[MAXN], st[MAXN][20];
inline int rmin(int a, int b){
	return dep[a]<dep[b]?a:b;
}
void add(int u, int v, int w){
	Edge *e=&mempool[memnum++];
	e->v=v,e->w=w,e->next=edge[u],edge[u]=e;
}
int getn(){
	char ch;
	int res=0;
	for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())
		res=res*10+ch-'0';
	return res;
}
void predfs(int now, int deep){
	dep[now]=deep;
	vis[now]=1;
	stack[++snum]=now;
	tree[++tnum]=now;
	tapp[now]=tnum;
	if(!app[now]) app[now]=snum;
	for(Edge *tmp=edge[now];tmp;tmp=tmp->next){
		if(!vis[tmp->v]){
			predfs(tmp->v,deep+1);
			stack[++snum]=now;
			son[now]+=son[tmp->v]+1;
		}
	}
}
void find(int i, int k){
	if(k==0){
		st[i][k]=stack[i];
		return;
	}
	if(!st[i][k-1]) find(i,k-1);
	if(!st[i+(1<<(k-1))][k-1]) find(i+(1<<(k-1)),k-1);
	st[i][k]=rmin(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
int rmq(int l, int r){
	int k=int(log(1.0*(r-l+1))/log(2.0)),kr=r-(1<<k)+1;
	if(!st[l][k]) find(l,k);
	if(!st[kr][k]) find(kr,k);
	return rmin(st[l][k], st[kr][k]);
}
int getsum(int x){
	int res=0;
	for(;x>0;x-=x&-x)
		res+=cnum[x];
	return res;
}
void add(int x, int d){
	for(;x<=n;x+=x&-x)
		cnum[x]+=d;
}
int lca(int a, int b){
	if(a==b) return a;
	int x=app[a], y=app[b];
	if(x<y) return rmq(x,y);
	else return rmq(y,x);
}
int dist(int now){
	return getsum(tapp[now]);
}
int ask(int a, int b){
	return dist(a)+dist(b)-2*dist(lca(a,b));
}
void change(int i, int w){
	int a=road[i][0], b=road[i][1];
	if(dep[a]>dep[b]){int tmp=a;a=b;b=tmp;}
	add(tapp[b], w-road[i][2]);
	add(tapp[b]+son[b]+1, road[i][2]-w);
	road[i][2]=w;
}
int main(){
	int u,a,b,w,c;
	scanf("%d %d %d\n",&n,&q,&cur);
	for(int i=1;i<n;++i){
		a=getn(), b=getn(), w=getn();
		add(a,b,w);
		add(b,a,w);
		road[i][0]=a;
		road[i][1]=b;
		road[i][2]=w;
	}
	predfs(1,0);
	for(int i=1;i<n;++i){
		w=road[i][2];
		road[i][2]=0;
		change(i,w);
	}
	for(int i=1;i<=q;++i){
		c=getn();
		if(!c){
			u=getn();
			printf("%d\n",ask(cur,u));
			cur=u;
		}else{
			a=getn(), b=getn();
			change(a,b);
		}
	}
	return 0;
}
Categories: OI Tags: , , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: