# [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.

Input:

```1

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

Output:

```1
3```

## Code: O(NlogN+Qlog2N) [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);
}
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;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai