[spoj QTREE 1~3] Query on a tree I-III

QTREE系列是spoj上一套维护树上信息的题目. 有两道QTREE3. - QTREE 1: 修改边权/询问路径上最大边权 - QTREE 2: 询问树上两点间路径/询问某路径上第k个点 - QTREE 3 - Query on a tree again!: 切换某点颜色(黑白)/询问1到某点的路径上首个黑点 - PT07J - Query on a tree III: 询问子树中权值第k大的点(保证唯一)

QTREE 1

我写了轻重链剖分 >_<

#define ALL 1, 1, dfs_clock

const int N = 1e4;

struct Edge {
	int v, w, nxt;
} E[N*2];

int dfs_clock, ptr = 1, adj[N+1], son[N+1], fa[N+1], w[N+1], top[N+1], dfn[N+1], seq[N+1], dep[N+1];

inline void add(int u, int v, int w)
{
	E[ptr] = (Edge){v, w, adj[u]};
	adj[u] = ptr++;
}

int get_son(int u)
{
	int sz = 1, mx = 0;
	son[u] = 0;
	for (int i = adj[u]; i; i = E[i].nxt) {
		int v = E[i].v;
		if (v != fa[u]) {
			w[v] = E[i].w;
			fa[v] = u;
			dep[v] = dep[u] + 1;
			int s = get_son(v);
			sz += s;
			if (s > mx) {
				son[u] = v;
				mx = s;
			}
		}
	}
	return sz;
}

void get_top(int u, int t)
{
	top[u] = t;
	seq[dfn[u] = ++dfs_clock] = u;
	if (!son[u]) return;
	get_top(son[u], t);
	for (int i = adj[u]; i; i = E[i].nxt) {
		int v = E[i].v;
		if (v != fa[u] && v != son[u])
			get_top(v, v);
	}
}

struct Seg {
	int mx[N*4];
	
	int build(int o, int l, int r)
	{
		if (l == r) return mx[o] = w[seq[l]];
		int m = (l+r)/2;
		return mx[o] = max(build(o*2, l, m), build(o*2+1, m+1, r));
	}

	int query(int L, int R, int o, int l, int r)
	{
		if (L <= l && r <= R) return mx[o];
		int ans = 0, m = (l+r)/2;
		if (L <= m) ans = query(L, R, o*2, l, m);
		if (R > m) ans = max(ans, query(L, R, o*2+1, m+1, r));
		return ans;
	}

	void modify(int x, int v, int o, int l, int r)
	{
		if (l == r) return mx[o] = v, void();
		int m = (l+r)/2;
		if (x <= m) modify(x, v, o*2, l, m);
		else modify(x, v, o*2+1, m+1, r);
		mx[o] = max(mx[o*2], mx[o*2+1]);
	}
} T;

int query(int x, int y)
{
	int ans = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) swap(x, y);
		ans = max(ans, T.query(dfn[top[y]], dfn[y], ALL));
		y = fa[top[y]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	return x == y ? ans : max(ans, T.query(dfn[x]+1, dfn[y], ALL));
}

inline void change(int k, int v)
{
	k *= 2;
	int x = fa[E[k].v] == E[k-1].v ? E[k].v : E[k-1].v;
	T.modify(dfn[x], v, ALL);
}

inline void init(int n)
{
	dfs_clock = 0;
	ptr = 1;
	fill_n(adj+1, n, 0);
}
	
int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		init(n);
		rep (i, 1, n) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		
		get_son(1);
		get_top(1, 1);

		T.build(ALL);
		
		char s[7];
		while (scanf("%s", s) == 1 && s[0] != 'D') {
			int a, b;
			scanf("%d%d", &a, &b);
			if (s[0] == 'Q')
				printf("%d\n", query(a, b));
			else
				change(a, b);
		}
	}
	return 0;
}

QTREE 2

我写了树上倍增 >_<

const int N = 1e4, D = 14;

struct Edge {
	int v, w, nxt;
} E[N*2];

int ptr = 1, maxd, adj[N+1], anc[N+1][D+1], dep[N+1], dis[N+1];

inline void add(int a, int b, int c)
{
	E[ptr] = (Edge){b, c, adj[a]};
	adj[a] = ptr++;
}

void dfs(int u, int p)
{
	anc[u][0] = p;
	rep (i, 1, maxd+1)
		anc[u][i] = anc[anc[u][i-1]][i-1];
	for (int i = adj[u]; i; i = E[i].nxt) {
		int v = E[i].v;
		if (v != p) {
			dis[v] = dis[u] + E[i].w;
			dep[v] = dep[u] + 1;
			dfs(v, u);
		}
	}
}

int up(int x, int h)
{
	for (int i = 0; h; h >>= 1, ++i)
		if (h & 1)
			x = anc[x][i];
	return x;
}

int lca(int x, int y)
{
	if (dep[x] > dep[y]) swap(x, y);
	y = up(y, dep[y]-dep[x]);
	if (x == y) return x;
	per (i, maxd, 0)
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	return anc[x][0];
}

inline void init(int n)
{
	ptr = 1;
	fill_n(adj+1, n, 0);
	for (maxd = 0; (1<<maxd) < n; ++maxd) ;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		init(n);
		rep (i, 0, n-1) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}

		dfs(1, 0);
		
		char s[5];
		while (scanf("%s", s) == 1 && s[1] != 'O') {
			int x, y, k;
			scanf("%d%d", &x, &y);
			int z = lca(x, y);
			if (s[0] == 'D')
				printf("%d\n", dis[x] + dis[y] - 2*dis[z]);
			else {
				scanf("%d", &k);
				printf("%d\n", dep[x] - dep[z] + 1 >= k
					   ? up(x, k-1) : up(y, dep[x] + dep[y] - 2*dep[z] + 1 - k));
			}
		}
	}
	return 0;
}

QTREE 3 - 1

我写了LCT >_<

由于现在注册spoj需要一些特殊手段, 而vjudge上没收录这道题, 所以还没提交, 暂时不贴代码.

QTREE 3 - 2

在DFS序上建可持久化线段树. 每个点只放一次, 记录子树大小以确定区间.

我没有写代码 >_<