首页 > 代码库 > HDU4836 The Query on the Tree(树状数组&&LCA)

HDU4836 The Query on the Tree(树状数组&&LCA)

2024-07-06 18:30:08   223人阅读

由于智力的问题，百度之星完全lu不动。。开场看第一题根据题目给的条件我觉得一定是可以构造出来的，题目给的意思颇有鸽巢原理的感觉，于是觉得开场第一题应该就是智力构造题了，想了半个小时，发现完全想不动，于是只能放弃了去想后面的题。

然后看第二题的数据结构，树上的询问，支持点修改，询问子树和，还有换根，然后心里想，我擦，这不是LCT么，但是我没学呀，然后细心的翻出之前打印的论文研读了很久，发现普通的LCT只能解决询问树路径上的东西，然后看论文上写如果支持子树操作的话就需要Euler-tour-tree什么的，想了一个多小时都想不到怎么用LCT，最后只能作罢。

然后看了三四题觉得也没什么思路，就去看第五题了，我感觉第五题是有思路的，对两个串建自动机，然后dp[i]定义为状态i的胜率，那么每个状态有两个转移边，转移到xi以及xj状态，那么dp[i]=1/2(dp[xi]+dp[xj]),然后边界就是我方胜利的状态为1，敌方胜利的状态为0，然后我希望能够通过发现图里深层的关系以期避免高斯消元，但是怎么搞都觉得是要高斯消元的，但是因为题目输出的是最简分数，分数版本的高斯消元我感觉我是写不粗来的，然后就只能作罢了。赛后听英姐说用LCM去消，我就明白了其实就是消元的时候按照高中学的那种消去法就好了，不要搞什么小数出来，有空写写看下能不能过。。

最后只能回头去看最多人过的第二题了，在纸上画了一下发现规律了，将原来的树保持不变，修改的时候按照传统的树状数组的点更段询就可以了，关键是在询问的时候，如果当前 询问的点是当前根的父亲，那么答案应该是 所有权值的和－（询问点包含根的那棵子树的和），否则就直接询问就可以了。要写一个LCA来求出询问点到根的路径的下一个点，然后每次询问都是logn的。

好久没写代码了呢，回头搜下看下第一题是怎么作粗来的。。

?
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
#define maxn 10050
#define maxlogv 16
int bit[maxn];
int n;
 
void add(int x, int v)
{
    while (x <= n){
        bit[x] += v;
        x += x&(-x);
    }
}
 
int query(int x)
{
    int ret = 0;
    while (x > 0){
        ret += bit[x];
        x -= x&(-x);
    }
    return ret;
}
 
 
int first[maxn];
int nxt[2 * maxn];
int vv[2 * maxn];
int e;
void addEdge(int u, int v)
{
    vv[e] = v; nxt[e] = first[u];
    first[u] = e++;
}
 
 
int pre[maxn];
int post[maxn];
vector<int> G[maxn];
int val[maxn];
int dfs_clock;
int p[maxn][maxlogv];
int dep[maxn];
 
 
void dfs(int u,int fa,int d)
{
    p[u][0] = fa; dep[u] = d;
    pre[u] = ++dfs_clock; int v;
    for (int i = first[u]; i !=-1; i=nxt[i]){
        v = vv[i];
        if (!pre[v]) dfs(v,u,d+1);
    }
    post[u] = dfs_clock;
}
 
void setRoot(int root)
{
    memset(pre, 0, sizeof(pre));
    memset(post, 0, sizeof(post));
    memset(p, -1, sizeof(p));
    memset(dep, 0, sizeof(dep));
    dfs_clock = 0;
    dfs(root,-1,0);
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= n; i++){
        add(pre[i], val[i]);
    }
}
 
void getp()
{
    for (int j = 0; j + 1 <= maxlogv; j++){
        for (int i = 1; i <= n; i++){
            if (p[i][j] != -1){
                p[i][j + 1] = p[p[i][j]][j];
            }
        }
    }
}
 
bool isFather(int u, int v)
{
    return pre[u] <= pre[v] && pre[v] <= post[u];
}
 
int findPostFather(int u, int v)
{
    int gap = dep[v] - dep[u];
    gap -= 1;
    for (int i = maxlogv; i >= 0; i--){
        if ((gap >> i) & 1){
            v = p[v][i];
        }
    }
    return v;
}
 
int main()
{
    int T; cin >> T; int ca = 0;
    while (T--)
    {
        scanf("%d", &n);
        int ui, vi;
        memset(first, -1, sizeof(first)); e = 0;
        for (int i = 0; i < n - 1; i++){
            scanf("%d%d", &ui, &vi);
            addEdge(ui, vi);
            addEdge(vi, ui);
        }
        int tot = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d", val + i);
            tot += val[i];
        }
        setRoot(1);
        int root = 1;
        getp();
        int m; scanf("%d", &m);
        char s[12];
        printf("Case #%d:\n", ++ca);
        for (int i = 0; i < m; i++){
            scanf("%s",s);
            if (s[0] == ‘Q‘){
                scanf("%d", &ui);
                if (ui == root) {
                    printf("%d\n", tot); continue;
                }
                if (isFather(ui, root)){
                    vi = findPostFather(ui,root);
                    printf("%d\n", tot - (query(post[vi]) - query(pre[vi] - 1)));
                }
                else{
                    printf("%d\n", query(post[ui]) - query(pre[ui] - 1));
                }
            }
            else if (s[0] == ‘C‘){
                scanf("%d%d", &ui, &vi);
                add(pre[ui], vi - val[ui]);
                tot += vi - val[ui];
                val[ui] = vi;
            }
            else{
                scanf("%d", &ui);
                root = ui;
            }
        }
    }
    return 0;
}

 


联系
我们