树上路径的权值之和 ural.txt

ACM资料大集合

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
#define PB push_back
#define PO pop_back
#define BG begin
#define ED end

//Ural
#define NMAX 100005
#define KMAX 17
int haoer[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};

typedef struct oopf
{
	int data;
	int where;
}oopf;
oopf f[NMAX][KMAX];//f[i][j]第i位开始，长度为2^(j-1)的最大值

typedef struct ooparc
{
	int first;
	int second;
}ooparc;

typedef struct oopnode
{
	int fa;
	int mv;
	int fnum;
	int st;
	int end;
	int go;
	int left,right;//后序编列中子树的起始点、终止点
}oopnode;

typedef struct ooptree
{
	int value;
//	int left;
//	int right;
}ooptree;

ooptree tree[4*NMAX];
int sum;

ooparc arc[2*NMAX];
oopnode node[NMAX+10];
typedef struct oopxulie
{
	int dian;
	int depth;
}oopxulie;
oopxulie xulie[2*NMAX];
oopxulie houxu[NMAX];
int cixu;
int houci;

void build_tree(int p,int left,int right)
{
	int mid=(left+right)/2;
//	tree[p].left=left;
//	tree[p].right=right;
//	tree[p].mid=(left+right)/2;
	tree[p].value=0;
	if(right-left>1)
	{
		build_tree(2*p,left,mid);
		build_tree(2*p+1,mid+1,right);
	}
}

void insert_tree(int p,int l,int r,int v,int left,int right)
{
	int mid=(left+right)/2;
	if(l==left && r==right) tree[p].value+=v; 
	else
	{
     if(r<=mid) insert_tree(2*p,l,r,v,left,mid);
	 else if(l>mid) insert_tree(2*p+1,l,r,v,mid+1,right);
	 else 
	 {
		 insert_tree(2*p,l,mid,v,left,mid);
		 insert_tree(2*p+1,mid+1,r,v,mid+1,right);
	 }
	}
}

int count(int p,int x,int left,int right)
{
	int mid=(left+right)/2;
	if(left==right) return tree[p].value;
	else
	{
		if(x<=mid) return tree[p].value+count(2*p,x,left,mid);
		else return tree[p].value+count(2*p+1,x,mid+1,right);
	}
}

bool cmpf(ooparc a,ooparc b)
{
	return a.first<b.first;
}

void init(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		f[i][0].data=xulie[i].depth;
		f[i][0].where=xulie[i].dian;
	}
	for(j=1;j<=KMAX;j++)
	{
		for(i=1;i<=num-haoer[j]+1;i++)
		{
			if(f[i][j-1].data<f[i+haoer[j-1]][j-1].data) 
			{f[i][j].data=f[i][j-1].data;f[i][j].where=f[i][j-1].where;}
			else {f[i][j].data=f[i+haoer[j-1]][j-1].data;f[i][j].where=f[i+haoer[j-1]][j-1].where;}
		}
	}
//	print(num);
}

int cal(int a,int b)
{
	double aa;
	int k;
	if(a>b) {k=a;a=b;b=k;}
	k=(int)(((double)(log10((double)(b-a))))/((double)log10(2.00))+0.000001);
//	printf("k=%d\n",k);
//	printf("a=%.2f  b=%.2f  %.5f %.5f",aa,bb,(double)(log10((double)aa-(double)bb)),(double)log10(2.00));
//	system("pause");
	if(f[a][k].data<f[b-haoer[k]+1][k].data) return f[a][k].where;
	else return f[b-haoer[k]+1][k].where;
}


void print_xu(int cixu)
{
	int i;
	for(i=1;i<=cixu;i++)
		printf("%d ",xulie[i].dian);
	printf("\n");
		for(i=1;i<=cixu;i++)
		printf("%d ",xulie[i].depth);
	printf("\n");
	for(i=1;i<=houci;i++)
		printf("%d ",houxu[i].dian);
	printf("\n");
}

void add(int x,int v)
{//x这个点加v
	node[x].mv+=v;
	insert_tree(1,node[x].left,node[x].right,v,1,NMAX);
}

int getans(int a,int b)
{
//	printf("a.go=%d b.go=%d\n",node[a].go,node[b].go);
	int rt=cal(node[a].go,node[b].go);
//	printf("a.right=%d b.right=%d rt=%d rt.right=%d\n",node[a].right,node[b].right,rt,node[rt].right);
	return count(1,node[a].right,1,NMAX)+count(1,node[b].right,1,NMAX)-2*count(1,node[rt].right,1,NMAX)+node[rt].mv;
}

void build(int root,int dep)
{
	int i;
	int s,t;
	s=houci+1;
	node[root].left=s;
//	printf("root=%d\n",root);
//	printf("xulie[%d]=%d \n",cixu,root);
	for(i=node[root].st;i<=node[root].end;i++)
	{
		if(node[arc[i].second].fa==0)
		{
			xulie[++cixu].dian=arc[i].second;
			xulie[cixu].depth=dep;
			node[arc[i].second].fa=root;
			node[arc[i].second].go=cixu;
//			printf("first=%d second=%d [%d].fa=%d\n",root,arc[i].second,arc[i].second,root);
			build(arc[i].second,dep+1);
			xulie[++cixu].dian=node[arc[i].second].fa;
			xulie[cixu].depth=dep-1;
		}
	}
//	printf("houci=%d %d\n",houci,root);
	houxu[++houci].dian=root;
	t=houci;
	node[root].right=t;
}

void solve(int num)
{
	int i,j,root;
	for(i=1;i<=num;i++) 
	{
		node[i].fa=0;
	   node[i].fnum=0;
	   node[i].mv=0;
	}
	for(i=1;i<=num-1;i++)
	{
		node[arc[i].first].fnum++;
		node[arc[i].second].fnum++;
	}	
//	for(i=1;i<=num;i++)
//	{
//		if(node[i].fnum==1) 
//		{root=i;break;}
//	}
	root=1;
	for(i=1;i<=num-1;i++)
	{
		arc[i+num-1].first=arc[i].second;
		arc[i+num-1].second=arc[i].first;
	}
	sort(arc+1,arc+2*num-1,cmpf);
	node[1].st=1;
	for(i=2,j=1;i<=2*num-2;i++)
	{
		if(arc[i].first!=arc[i-1].first)
		{node[j].end=i-1;j++;node[j].st=i;}	
	}
	node[j].end=2*num-2;
//	for(i=1;i<=num;i++) 
//	{printf("st=%d end=%d\n",node[i].st,node[i].end);}
	cixu=0;
	houci=0;
	xulie[++cixu].dian=root;
	xulie[cixu].depth=0;
	node[root].go=1;
//	printf("root=%d\n",root);
	node[root].fa=-1;
	build(root,1);
//	print_xu(cixu);
	init(cixu);
	build_tree(1,1,NMAX);
}

int main()
{
	int i,num,qnum,qa,qb;
	char qq[3];
	scanf("%d",&num);
	for(i=1;i<=num-1;i++) scanf("%d %d",&arc[i].first,&arc[i].second);
	solve(num);
//	printf("go\n");
//	for(i=1;i<=num;i++) printf("%d ",node[i].go);
//	printf("\n");
//	printf("houci st end\n");
//	for(i=1;i<=num;i++) printf("st=%d end=%d\n",node[i].left,node[i].right);
//	printf("\n");
	scanf("%d",&qnum);
	for(i=1;i<=qnum;i++)
	{
		scanf("%s %d %d",qq,&qa,&qb);
		if(qq[0]=='I') add(qa,qb);
		else printf("%d\n",getans(qa,qb));
	}
	return 0;
}