盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5296 Annoying problem(LCA+点到链的最短距离)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5296

题意

给定n个点的树,q个询问。维护一个集合s,有两种操作
1 u,表示选中树上的点u,加入集合
2 u,表示取消选中点u,从集合中删除
对于每个操作输出:
使得选中的点联通的边权和是多少。

思路

题解:

代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 100010;
int dep[N], dfn[N], rdfn[N], f[17][N], lev, dist[N];
bool in[N];
vector< pair<int, int> > g[N];
int T, n, q, cnt;
set<int> s;
void dfs(int u, int fa) {
dfn[u] = ++cnt;
rdfn[cnt] = u;
dep[u] = dep[fa] + 1;
f[0][u] = fa;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].fi, w = g[u][i].se;
if (v == fa) continue;
dist[v] = dist[u] + w;
dfs(v, u);
}
}
void st() {
int i, j;
for (j = 1; 1 << j < n; j++)
for (i = 1; i <= n; i++)
f[j][i] = f[j - 1][f[j - 1][i]];
lev = j - 1;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int i = lev; i >= 0; i--)
if (d >> i & 1)
x = f[i][x];
if (x == y) return x;
for (int i = lev; i >= 0; i--)
if (f[i][x] != f[i][y])
x = f[i][x], y = f[i][y];
return f[0][x];
}
int add(int u) {
if (s.empty()) return 0;
set<int> :: iterator it = s.lower_bound(dfn[u]), it1 = it;
it1--;
if (it == s.begin() || it == s.end()) {
it = s.begin();
it1 = s.end();
it1--;
}
int x = *it, y = *it1;
x = rdfn[x], y =rdfn[y];
return dist[u] - dist[lca(x, u)] - dist[lca(y, u)] + dist[lca(x, y)];
}
int main () {
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) g[i].clear(), in[i] = false;
int u, v, w;
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
g[u].pb({v, w});
g[v].pb({u, w});
}
printf("Case #%d:\n", cas);
cnt = 0;
dfs(1, 0);
st();
s.clear();
int ans = 0;
while(q--) {
scanf("%d%d", &v, &u);
if (v == 1) {
if (!in[u]) {
ans += add(u);
s.insert(dfn[u]);
in[u] = true;
}
} else {
if (in[u]) {
s.erase(dfn[u]);
ans -= add(u);
in[u] = false;
}
}
printf("%d\n", ans);
}
}
return 0;
}

更新日志

  • 14120982 2015-07-22 22:49:10 Accepted 5296 2433MS 21724K 2510 B G++ SIO__Five