1036: [ZJOI2008]树的统计Count 树链剖分裸题

Tags: c++

题目链接:http://www.lydsy.com/JudgeOnline/status.php?user_id=a654889339

树链剖分裸题:

#include
#include
#include
#include
#define N 60003
#define L(x) (x>1)
#define inf 10000000
using namespace std;

struct Edge{
	int to, nex;
}edge[N*2];
int head[N], edgenum;
void add(int u, int v){
	Edge E={v,head[u]}; 	edge[edgenum] = E; 	head[u] = edgenum++;
}

int n, Query, a[N];

int fa[N];//父节点
int dep[N];//深度
int son[N];//重儿子
int size[N];//子树节点数
int p[N]; //p[v]表示v在线段树中的位置
int fp[N]; //与p数组相反
int top[N]; // top[v] 表示v所在的重链的顶端节点 (这样 v与top[v] 的重路径可以直接在线段树上操作)lkjiyhtrf saQ

int dfs(int u, int Father, int deep){
	fa[u] = Father;		size[u] = 1;	dep[u] = deep;
	for(int i = head[u]; ~i; i = edge[i].nex){
		int v = edge[i].to;
		if(v == Father)continue;
		size[u] += dfs(v, u, deep+1);
		if(son[u] == -1 || size[v] > size[son[u]])son[u] = v;
	}
	return size[u];
}

int tree_id; //tree_id表示线段树中所有的边(给每条边编号)
void Have_p(int u, int Father){
	top[u] = Father;
	p[u] = tree_id++; fp[p[u]] = u;
	if(son[u] == -1)return ;
	Have_p(son[u], top[u]); //注意这里
	for(int i = head[u]; ~i; i = edge[i].nex){
		int v = edge[i].to;
		if(v != son[u] && v != fa[u])Have_p(v, v); //注意这里
	}
}

struct node{
	int l, r;
	int Max, Sum;
}tree[N*8];
void push_up(int id){
	tree[id].Max = max(tree[L(id)].Max, tree[R(id)].Max);
	tree[id].Sum = tree[L(id)].Sum + tree[R(id)].Sum;
}
void build(int l, int r, int id){
	tree[id].l = l, tree[id].r = r;
	if(l == r)
	{
		tree[id].Sum = tree[id].Max = a[fp[l]]; //注意这里
		return ;
	}
	int mid = Mid(l, r);
	build(l, mid, L(id));
	build(mid+1, r, R(id));
	push_up(id);
}

void updata(int pos, int val, int id){
	if(tree[id].l == tree[id].r)
	{
		tree[id].Max = tree[id].Sum = val;
		return ;
	}
	int mid = Mid(tree[id].l, tree[id].r);
	if(pos  dep[v])swap(u, v); //注意这里
	return tmp + querySum(p[u], p[v], 1);
}
int findMax(int u, int v){
	int f1 = top[u], f2 = top[v];
	int tmp = -inf;
	while(f1 != f2)
	{
		if(dep[f1] dep[v])swap(u, v);
	return max(tmp, queryMax(p[u], p[v], 1));
}

void init(){
	memset(head, -1, sizeof(head));
	memset(son, -1, sizeof(son));  //注意这里son初始化
	edgenum = 0;
	tree_id = 1; //这个的所有可用编号就是线段树的区间 注意这里是从1开始的
}
char op[10];
int main(){
	int u, v, i;
	while(~scanf("%d",&n)){
		init();
		for(i = 0; i 


本文链接:http://www.4byte.cn/learning/58673.html