HDU 5044 Tree

field=problem&key=2014+ACM%2FICPC+Asia+Regional+Shanghai+Online&source=1&searchmode=source" target="_blank" style="">题目链接

就简单的树链剖分，只是坑要加输入外挂，还要手动扩栈

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 100005;

#pragma comment(linker, "/STACK:1024000000,1024000000")

void scanf_(int &num) {

	char in;

	bool neg=false;

	while(((in=getchar()) > '9' || in<'0') && in!='-') ;

	if(in=='-')

	{

		neg=true;

		while((in=getchar()) >'9' || in<'0');

	}

	num=in-'0';

	while(in=getchar(),in>='0'&&in<='9')

		num*=10,num+=in-'0';

	if(neg)

		num=0-num;

}

int dep[N], fa[N], son[N], sz[N], top[N], id[N], idx, val[N];

int first[N], next[N * 2], vv[N * 2], en;

int bit[2][N];

void init() {

	en = 0;

	idx = 0;

	memset(first, -1, sizeof(first));

	memset(bit, 0, sizeof(bit));

}

void add_Edge(int u, int v) {

	vv[en] = v;

	next[en] = first[u];

	first[u] = en++;

}

void dfs1(int u, int f, int d) {

	dep[u] = d;

	sz[u] = 1;

	fa[u] = f;

	son[u] = 0;

	for (int i = first[u]; i + 1; i = next[i]) {

		int v = vv[i];

		if (v == f) continue;

		dfs1(v, u, d + 1);

		sz[u] += sz[v];

		if (sz[son[u]] < sz[v])

			son[u] = v;

	}

}

void dfs2(int u, int tp) {

	id[u] = ++idx;

	top[u] = tp;

	if (son[u]) dfs2(son[u], tp);

	for (int i = first[u]; i + 1; i = next[i]) {

		int v = vv[i];

		if (v == fa[u] || v == son[u]) continue;

		dfs2(v, v);

	}

}

inline int lowbit(int x) {

	return x&(-x);

}

void add(int ty, int x, int v) {

	while (x < N) {

		bit[ty][x] += v;

		x += lowbit(x);

	}

}

void add(int ty, int l, int r, int v) {

	add(ty, l, v);

	add(ty, r + 1, -v);

}

int get(int ty, int x) {

	int ans = 0;

	while (x) {

		ans += bit[ty][x];

		x -= lowbit(x);

	}

	return ans;

}

void gao(int ty, int u, int v, int w) {

	int tp1 = top[u], tp2 = top[v];

	while (tp1 != tp2) {

		if (dep[tp1] < dep[tp2]) {

			swap(tp1, tp2);

			swap(u, v);

		}

		add(ty, id[tp1], id[u], w);

		u = fa[tp1];

		tp1 = top[u];

	}

	if (dep[u] > dep[v]) swap(u, v);

	if (ty == 1) {

		if (u != v)

			add(ty, id[son[u]], id[v], w);

	} else add(ty, id[u], id[v], w);

}

int T, n, m, s[N], t[N];

int main() {

	int cas = 0;

	scanf("%d", &T);

	while (T--) {

		init();

		scanf("%d%d", &n, &m);

		for (int i = 1; i < n; i++) {

			scanf_(s[i]); scanf_(t[i]);

			add_Edge(s[i], t[i]);

			add_Edge(t[i], s[i]);

		}

		dfs1(1, 0, 1);

		dfs2(1, 1);

		for (int i = 1; i < n; i++) {

			if (dep[s[i]] < dep[t[i]])

				swap(s[i], t[i]);

		}

		char Q[10];

		int u, v, k;

		while (m--) {

			scanf("%s", Q);

			scanf_(u); scanf_(v); scanf_(k);

			if (Q[3] == '1') gao(0, u, v, k);

			else gao(1, u, v, k);

		}

		printf("Case #%d:\n", ++cas);

		for (int i = 1; i <= n; i++)

			printf("%d%c", get(0, id[i]), i == n ? '\n' : ' ');

		for (int i = 1; i < n; i++)

			printf("%d%c", get(1, id[s[i]]), i == n - 1 ? '\n' : ' ');

		if (n == 1) printf("\n");

	}

	return 0;

}