SPOJ – QTREE Query on a tree

Posted on | In ,

思路：
树链剖分模板题，TLE11次结果发现是自己细节上蠢了。。
树链剖分的原理

树链剖分是对一棵树进行轻重链划分，然后使用数据结构来维护每条链的一种算法。通常是为了解决树上点到点（也可以是点到边）值的更新与查询。在树链剖分中，核心的算法是两次dfs。第一次dfs我们对每个节点都确定其儿子节点中最“重”的节点（也就是size最大的节点），并记录一些关键信息，如深度，父亲节点等。第二次中我们对树上节点重新编号（因为优先对重儿子赋值，使得其id在线段树上连续，使得更新更加方便），同时确定其祖先节点。重儿子的祖先是其父亲的祖先，轻儿子的祖先是自己。在查询的过程中，如果两个节点的祖先节点相同，那么我们显然可以直接在线段树上查询，而不同的话我们就先更新其到其祖先节点的val，然后用之前记录的父亲节点爬到另一根链上（这里要注意，要优先用depth较深的节点进行更新）。这样交替进行直到成为我们之前碰到的两个点在一条链上，最后完成查询。

本题思路

本题与常规提不同，查询的是边的权值。碰到这种情况我们通常把边权值赋到较低的节点上，转换成点的问题。本题还闲得蛋疼卡string和cin，需要注意。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#pragma warning(disable:4996)
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)

using namespace std;
const int MAXN = 10005;
vector<pair<int, int>> v[MAXN];
struct edge {
    int f, t, val;
}EDGES[MAXN];
int tid[MAXN * 2], dep[MAXN * 2], fa[MAXN * 2], son[MAXN*2],sizes[MAXN*2],top[MAXN*2],label,n;
void dfs(int root, int father, int depth) {
    int maxsize = 0;
    fa[root] = father, dep[root] = depth, sizes[root] = 1,son[root]=0;
    for (vector<pair<int, int>>::iterator it = v[root].begin();it != v[root].end();it++) {
        if (it->first == father)continue;
        dfs(it->first, root, depth + 1);
        sizes[root] += sizes[it->first];
        if (sizes[it->first] > maxsize)maxsize = sizes[it->first], son[root] = it->first;
    }
}
void dfs2(int root, int father, int ancestor) {
    tid[root] = ++label,top[root]=ancestor;
    if (son[root]!=0)dfs2(son[root], root, ancestor);
    for (vector<pair<int, int>>::iterator it = v[root].begin();it != v[root].end();it++) {
        if (it->first == father || it->first == son[root])continue;
        dfs2(it->first, root, it->first);
    }
}
int tree[MAXN * 4];
void update(int root, int l, int r, int pos, int val) {
    if (l == r&&l == pos) tree[root] = val;
    else {
        int mid = (l + r) / 2;
        if (pos <= mid)update(root * 2, l, mid, pos, val);
        else update(root * 2 + 1, mid + 1, r, pos, val);
        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }
}
int query(int root, int l, int r, int ql,int qr) {
    if (ql <= l&&qr >= r)return tree[root];
    else {
        int mid = (l + r) / 2;
        if (qr <= mid)return query(root * 2, l, mid, ql, qr);
        else if (ql > mid)return query(root * 2 + 1, mid + 1, r, ql, qr);
        else return max(query(root * 2, l, mid, ql, qr), query(root * 2 + 1, mid + 1, r, ql, qr));
    }
}
int ask(int x, int y) {
    int i = x, j = y,maxs=-INF;
    while (top[i] != top[j]) {
        if (dep[top[i]] < dep[top[j]])swap(i, j);
        maxs=max(maxs,query(1, 1, n, tid[top[i]], tid[i]));
        i = fa[top[i]];
    }
    if (i == j)return maxs;
    if (dep[i] > dep[j])swap(i, j);
    maxs = max(maxs, query(1, 1, n, tid[son[i]], tid[j]));
    return maxs;
}
int main() {
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int k,f,t,val,pos,left,right;
    char str[105];
    scanf("%d", &k);
    while (k--) {
        for (int i = 0;i < MAXN;i++)v[i].clear();
        ms(tid, 0), ms(dep, 0), ms(fa, 0), ms(son, 0), ms(sizes, 0), ms(top, 0), ms(tree,-1);
        label = 0;
        scanf("%d", &n);
        for (int i = 0;i < n - 1;i++) {
            scanf("%d%d%d", &f, &t, &val);
            v[f].push_back(make_pair(t, val)), v[t].push_back(make_pair(f, val));
            EDGES[i] = { f,t,val };

        }
        dfs(1,0,0);
        dfs2(1,1,1);
        //update(1, 1, n, tid[1], -INF);
        for (int i = 0;i < n - 1;i++) {
            int u = dep[EDGES[i].f] > dep[EDGES[i].t] ? tid[EDGES[i].f] : tid[EDGES[i].t];
            update(1, 1, n, u, EDGES[i].val);
        }
        while (scanf("%s", str)!=EOF) {
            if (str[0] == 'D')break;
            else if (str[0] == 'C') {
                scanf("%d%d", &pos, &val);
                int u = dep[EDGES[pos-1].f] > dep[EDGES[pos-1].t] ? tid[EDGES[pos - 1].f] : tid[EDGES[pos - 1].t];
                update(1, 1, n, u, val);
            }
            else {
                scanf("%d%d", &left, &right);
                printf("%d\n", ask(left, right));
            }
        }
    }
    return 0;
}