[SPOJ QTREE] Query on a tree【树链剖分】

• 2018-04-09
• 0
• 0

Problem:

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

• CHANGE i ti : change the cost of the i-th edge to ti
  or
• QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000),
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
• The next lines contain instructions "CHANGE i ti" or "QUERY a b",
• The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

Output

For each "QUERY" operation, write one integer representing its result.

Example

Input:

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:

1
3

Solution:

本题也是树链剖分的模板题，只需将边权作为终点的点权即可转化为普通模型。

关于树剖的普通模型解法，详见 树链剖分模板。

Code: O(NlogN+Qlog²N) [18M, 0.20S]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 10005
using namespace std;

inline void getint(int &num){
	char ch; bool neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
	if(neg) num = -num;
}

int T, N, tope;
char opt[15];
int w[MAXN], dep[MAXN], fa[MAXN], sz[MAXN], hson[MAXN];
int dfn[MAXN], dfstime, top[MAXN], wt[MAXN], sub[MAXN];
int mx[MAXN << 2];
#define lc (u << 1)
#define rc (u << 1 | 1)

inline void update(int u) {mx[u] = max(mx[lc], mx[rc]);}

inline void build(int u, int l, int r){
	if(l == r) {mx[u] = wt[l]; return;}
	int mid = l + r >> 1;
	if(l <= mid) build(lc, l, mid); else mx[lc] = 0xc0c0c0c0;
	if(mid < r) build(rc, mid + 1, r); else mx[rc] = 0xc0c0c0c0;
	update(u);
}

inline void modify(int pos, int v){
	int u = 1, l = 1, r = N, *stk = new int[20], tops = 0;
	pos = dfn[pos];
	while(l < r){
		stk[tops++] = u;
		int mid = l + r >> 1;
		if(pos <= mid) u = lc, r = mid;
		else u = rc, l = mid + 1;
	}
	mx[u] = v;
	while(tops) update(stk[--tops]);
	delete []stk;
}

inline int query_max(int u, int l, int r, int ql, int qr){
	if(l == ql && r == qr) return mx[u];
	int mid = l + r >> 1;
	if(qr <= mid) return query_max(lc, l, mid, ql, qr);
	else if(ql > mid) return query_max(rc, mid + 1, r, ql, qr);
	else return max(query_max(lc, l, mid, ql, mid), query_max(rc, mid + 1, r, mid + 1, qr));
}

struct Edge{
	int id, np, val;
	Edge *nxt;
} E[MAXN << 1], *V[MAXN]; 

inline void clear_tree() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int i, int u, int v, int w){
	E[++tope].id = i, E[tope].np = v, E[tope].val = w;
	E[tope].nxt = V[u], V[u] = &E[tope];
}

inline void dfs1(int u, int f, int d){
	dep[u] = d, fa[u] = f, sz[u] = 1, hson[u] = 0;
	for(register Edge *ne = V[u]; ne; ne = ne->nxt){
		if(ne->np == f) continue;
		dfs1(ne->np, u, d + 1);
		w[ne->np] = ne->val, sub[ne->id] = ne->np;  // 将边权转化为点权, 并记录第 i 条边指向的点 
		sz[u] += sz[ne->np];
		if(sz[ne->np] > sz[hson[u]]) hson[u] = ne->np;
	}
}

inline void dfs2(int u, int tp){
	top[u] = tp, dfn[u] = ++dfstime, wt[dfstime] = w[u];
	if(!hson[u]) return;
	dfs2(hson[u], tp);
	for(register Edge *ne = V[u]; ne; ne = ne->nxt)
		if(ne->np != fa[u] && ne->np != hson[u]) dfs2(ne->np, ne->np);
}

inline int query(int u, int v){
	int res = 0xc0c0c0c0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		res = max(res, query_max(1, 1, N, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u != v){
		if(dep[u] > dep[v]) swap(u, v);
		res = max(res, query_max(1, 1, N, dfn[hson[u]], dfn[v]));
	}
	return res;
}

int main(){
	getint(T);
	while(T--){
		clear_tree(), getint(N);
		for(register int i = 1; i < N; i++){
			int u, v, w; getint(u), getint(v), getint(w);
			addedge(i, u, v, w), addedge(i, v, u, w);
		}
		dfs1(1, 0, 1), dfstime = 0, dfs2(1, 1), build(1, 1, N);
		for(scanf("%s", opt); opt[0] != 'D'; scanf("%s", opt)){
			int u, v; getint(u), getint(v);
			if(opt[0] == 'Q') printf("%d\n", query(u, v));
			else if(opt[0] == 'C') modify(sub[u], v);
		}
	}
	return 0;
}