HDU 5296 Annoying problem(LCA)

题意:

$N,Q\le 10^5,给定N个点的一棵树,边权C_i \le 100$
$Q次操作一个集合,输出每次操作后使得集合中点两两连通的最小边权和:$
$1 u:如果u不在集合中,则加入u$
$2 u:如果u不在集合中,则删除u$

分析:

$手玩一下可以发现,其实就是加入点或者删除点到最近的一条链的边权和$
$然后如何找呢,详细看这个博客吧,讲得很清楚:$传送门
$根据dfs序来确定选择的链,如果集合中的dfs序比当前点u都大或者小,就取dfs最大点和最小点$
$反之,就选大于它的dfs序的第一个点和小于它的最大的那个点$
$点到链的最短距离:$

代码:

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
//
// Created by TaoSama on 2016-04-26
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, q;
struct Edge {
int v, c;
};
vector<Edge> G[N];
const int LOG = 17;
int dfn[N], dfsNum;
int dep[N], dis[N], p[LOG][N];
void dfs(int u, int fa) {
dfn[u] = ++dfsNum;
p[0][u] = fa;
for(int i = 1; i < LOG; ++i) p[i][u] = p[i - 1][p[i - 1][u]];
for(Edge& e : G[u]) {
int v = e.v, c = e.c;
if(v == fa) continue;
dep[v] = dep[u] + 1;
dis[v] = dis[u] + c;
dfs(v, u);
}
}
int lca(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
for(int i = 0; i < LOG; ++i)
if(dep[v] - dep[u] >> i & 1) v = p[i][v];
if(u == v) return u;
for(int i = LOG - 1; ~i; --i)
if(p[i][u] != p[i][v])
u = p[i][u], v = p[i][v];
return p[0][u];
}
//dis(u, x, y) = (dis(u, x) + dis(u, y) - dis(x, y)) / 2
//dis(u)+dis(x)-2dis(lca(u,x)) + dis(u)+dis(y)-2dis(lca(u,y))
//-dis(x)-dis(y)+2*dis(lca(x,y))
//vertex to chain
int get(int u, int x, int y) {
return dis[u] - dis[lca(u, x)] - dis[lca(u, y)] + dis[lca(x, y)];
}
int gao(int u, set<pair<int, int> >& s) {
if(!s.size()) return 0;
int x, y;
auto iter = s.lower_bound({dfn[u], u});
if(iter == s.end() || iter == s.begin()) {
x = s.begin()->second;
y = s.rbegin()->second;
} else {
x = iter->second;
--iter;
y = iter->second;
}
return get(u, x, y);
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i) G[i].clear();
for(int i = 1; i < n; ++i) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
G[u].push_back({v, c});
G[v].push_back({u, c});
}
dfsNum = 0;
dfs(1, 0);
static int kase = 0;
printf("Case #%d:\n", ++kase);
set<pair<int, int> > s;
int ans = 0;
while(q--) {
int op, u; scanf("%d%d", &op, &u);
if(op == 1) {
if(!s.count({dfn[u], u})) {
ans += gao(u, s);
s.insert({dfn[u], u});
}
} else {
if(s.count({dfn[u], u})) {
s.erase({dfn[u], u});
ans -= gao(u, s);
}
}
printf("%d\n", ans);
}
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到