HDU5173 GTY's game II

bc的题。今天bc又挂了。这题没有写完，然后b题fst了。伤心啊。

其实思路比较简单。直接链剖dfs序上把所有区间找出来swap就好了。不过代码实现起来还是比较麻烦的，很容易绕晕。加上smt久了没写手生了，于是就调了一晚上。唉，我还是太年轻了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

struct node {
	int v, s, sz, w, rv;
	node *ls, *rs;
	inline void update() {
		sz = 1;
		s = v;
		if (ls) {
			sz += ls-> sz;
			s += ls-> s;
		}
		if (rs) {
			sz += rs-> sz;
			s += rs-> s;
		}
	}
	inline void fix() {
		if (rv) {
			swap(ls, rs);
			if (ls)
				ls-> rv ^= 1;
			if (rs)
				rs-> rv ^= 1;
			rv = 0;
		}
	}
};
typedef pair <node*, node*> npr;

const int maxn = 80009;

#define szof(p) ((p)?(p->sz):0)
#define sof(p) ((p)?(p->s):0)
node nlst[maxn << 1], *np(nlst);
node* newNode(int v) {
	np-> ls = np-> rs = 0;
	np-> v = np-> s = v;
	np-> sz = 1;
	np-> rv = 0;
#ifdef WIN32
	np-> w = (rand() << 16) | rand();
#else
	np-> w = rand();
#endif
	return np ++;
}
node* merge(node* p, node* q) {
	if (p)
		p-> fix();
	else
		return q;
	if (q)
		q-> fix();
	else
		return p;
	if (p-> w > q-> w) {
		p-> rs = merge(p-> rs, q);
		p-> update();
		return p;
	}
	else {
		q-> ls = merge(p, q-> ls);
		q-> update();
		return q;
	}
}
npr split(node* p, int k) {
	if (!k)
		return npr(0, p);
	else if (!p || p-> sz == k)
		return npr(p, 0);
	else {
		p-> fix();
		if (k <= szof(p-> ls)) {
			npr g(split(p-> ls, k));
			p-> ls = g. second;
			p-> update();
			return npr(g. first, p);
		}
		else {
			npr g(split(p-> rs, k - szof(p-> ls) - 1));
			p-> rs = g. first;
			p-> update();
			return npr(p, g. second);
		}
	}
}
int smtQry(node* p, int k) {
	int s(0);
	while (p && k) {
		p-> fix();
		if (k <= szof(p-> ls))
			p = p-> ls;
		else
			s += sof(p-> ls) + p-> v, k -= szof(p-> ls) + 1, p = p-> rs;
	}
	return s;
}

struct edge {
	int t;
	edge *next;
};
edge *head[maxn], elst[maxn << 1], *ep(elst);
inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

int v[maxn], n, m;
int tc, fa[maxn], d[maxn], sz[maxn], fs[maxn], fc[maxn], ch[maxn];
int dfb[maxn], dfo[maxn];
node *rt, *remp;

void divide() {
	static int stc[maxn];
	int tst(1), dfn(0);
	memset(fa, 0, sizeof(fa));
	stc[tst] = 1;
	while (tst) {
		int p(stc[tst --]);
		dfo[++ dfn] = p;
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> t ^ fa[p]) {
				fa[e-> t] = p;
				d[e-> t] = d[p] + 1;
				stc[++ tst] = e-> t;
			}
	}
	tc = 0;
	for (int i = n; i; -- i) {
		int p(dfo[i]);
		fs[p] = -1;
		sz[p] = 1;
		for (edge* e = head[p]; e; e = e-> next)
			if (fa[e-> t] == p) {
				sz[p] += sz[e-> t];
				if (fs[p] == -1 || sz[e-> t] > sz[fs[p]])
					fs[p] = e-> t;
			}
		if (fs[p] == -1)
			fc[p] = ++ tc;
		else
			fc[p] = fc[fs[p]];
		ch[fc[p]] = p;
	}
	stc[tst = 1] = 1;
	dfn = 0;
	while (tst) {
		int p(stc[tst --]);
		dfo[++ dfn] = p;
		dfb[p] = dfn;
		for (edge* e = head[p]; e; e = e-> next)
			if (fa[e-> t] == p && e-> t != fs[p])
				stc[++ tst] = e-> t;
		if (fs[p] != -1)
			stc[++ tst] = fs[p];
	}
	rt = 0;
	for (int i = 1; i <= n; ++ i)
		rt = merge(rt, newNode(v[dfo[i]]));
	remp = 0;
	for (int i = 1; i <= n; ++ i)
		remp = merge(remp, newNode(-1));
}

int query(int u, int v) {
	int s(0);
	while (fc[u] ^ fc[v])
		if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
			s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[ch[fc[u]]] - 1);
			u = fa[ch[fc[u]]];
		}
		else {
			s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[ch[fc[v]]] - 1);
			v = fa[ch[fc[v]]];
		}
	if (d[u] < d[v])
		s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[u] - 1);
	else
		s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[v] - 1);
	return s;
}

bool checkTree(node* p, char e) {
	if (p) {
		if (p-> rv) {
			checkTree(p-> rs, 32);
			printf("%d%c", p-> v, e);
			checkTree(p-> ls, 32);
		}
		else {
			checkTree(p-> ls, 32);
			printf("%d%c", p-> v, e);
			checkTree(p-> rs, 32);
		}
	}
	return 0;
}

typedef pair <int, int> rpr;
rpr ra[maxn], rb[maxn];
void flip(int u, int v) {
	int tra(0), trb(0);
	while (fc[u] ^ fc[v]) {
		if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
			ra[tra ++] = rpr(dfb[ch[fc[u]]], dfb[u]);
			u = fa[ch[fc[u]]];
		}
		else {
			rb[trb ++] = rpr(dfb[ch[fc[v]]], dfb[v]);
			v = fa[ch[fc[v]]];
		}
	}
	if (d[u] < d[v])
		rb[trb ++] = rpr(dfb[u], dfb[v]);
	else
		ra[tra ++] = rpr(dfb[v], dfb[u]);
	node *cr(0);
	for (int i = 0; i < tra; ++ i) {
		npr x = split(rt, ra[i]. first - 1);
		npr y = split(x. second, ra[i]. second - ra[i]. first + 1);
		cr = merge(y. first, cr);
		npr z = split(remp, ra[i]. second - ra[i]. first + 1);
		remp = z. second;
		x. second = merge(z. first, y. second);
		rt = merge(x. first, x. second);
	}
	if (cr)
		cr-> rv ^= 1;
	for (int i = trb - 1; i >= 0; -- i) {
		npr x = split(rt, rb[i]. first - 1);
		npr y = split(x. second, rb[i]. second - rb[i]. first + 1);
		cr = merge(cr, y. first);
		npr z = split(remp, rb[i]. second - rb[i]. first + 1);
		remp = z. second;
		x. second = merge(z. first, y. second);
		rt = merge(x. first, x. second);
	}
	if (cr)
		cr-> rv ^= 1;
	for (int i = 0; i < tra; ++ i) {
		npr x = split(rt, ra[i]. first - 1);
		npr y = split(x. second, ra[i]. second - ra[i]. first + 1);
		npr z = split(cr, ra[i]. second - ra[i]. first + 1);
		cr = z. second;
		if (z. first)
			z. first-> rv ^= 1;
		x. second = merge(z. first, y. second);
		rt = merge(x. first, x. second);
		remp = merge(remp, y. first);
	}
	if (cr)
		cr-> rv ^= 1;
	for (int i = 0; i < trb; ++ i) {
		npr x = split(rt, rb[i]. first - 1);
		npr y = split(x. second, rb[i]. second - rb[i]. first + 1);
		npr z = split(cr, rb[i]. second - rb[i]. first + 1);
		cr = z. second;
		if (z. first)
			z. first-> rv ^= 1;
		x. second = merge(z. first, y. second);
		rt = merge(x. first, x. second);
		remp = merge(remp, y. first);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	memset(head, 0, sizeof(head));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i)
		scanf("%d", v + i);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
	}
	divide();
	while (m --) {
		int opt, u, v;
		scanf("%d%d%d", &opt, &u, &v);
		if (opt == 0)
			printf("%d\n", query(u, v));
		else
			flip(u, v);
	}
}