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

HDU 5293 Tree chain problem(树dp,lca,树状数组)

题目

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

题意

给定n个点的树,其中m条链有权值。现在需要选择一些链,使得其和最大。并且任意两条链之间没有公共点。1 ≤ n, m ≤ 100000

思路

题解:

代码

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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#define pb push_back
using namespace std;
const int N = 100000 + 100;
int t, n, m, cnt, lev;
int l[N], r[N], dep[N];
int f[20][N];
vector<int> g[N];
void dfs(int u, int fa) {
l[u] = ++cnt;
dep[u] = dep[fa] + 1;
if (fa != 0) f[0][u] = fa;
else f[0][u] = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) continue;
dfs(v, u);
}
r[u] = ++cnt;
}
void st() {
int i, j;
for (j = 1; 1 << j < n; j++)
for (int 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 cs[N * 2], cd[N * 2];
int sum[N], d[N];
struct node {
int u, v, lca, val;
}p[N];
vector<int> e[N];
int lowbit(int x) {
return x & (-x);
}
void add(int p, int va, int *c) {
while(p <= 2 * n) {
c[p] += va;
p += lowbit(p);
}
}
int getsum(int p, int *c) {
int res = 0;
while(p) {
res += c[p];
p -= lowbit(p);
}
return res;
}
void solve(int u, int fa) {
sum[u] = d[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) continue;
solve(v, u);
sum[u] += d[v];
}
d[u] = sum[u];
for (int i = 0; i < e[u].size(); i++) {
int x = p[e[u][i]].u;
int y = p[e[u][i]].v;
int tmp = getsum(l[x], cs) + getsum(l[y], cs) - getsum(l[x], cd) - getsum(l[y], cd) + sum[u];
d[u] = max(d[u], tmp + p[e[u][i]].val);
}
add(l[u], d[u], cd);
add(r[u], -d[u], cd);
add(l[u], sum[u], cs);
add(r[u], -sum[u], cs);
}
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
cs[0] = cd[0] = 0;
for (int i = 1; i <= n; i++) {
int j = 2 * i - 1;
cs[j] = cs[j + 1] = cd[j] = cd[j + 1] = 0;
g[i].clear();
e[i].clear();
}
int u, v;
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v); g[v].pb(u);
}
cnt = 0;
dep[0] = 0;
dfs(1, 0);
st();
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &p[i].u, &p[i].v, &p[i].val);
p[i].lca = lca(p[i].u, p[i].v);
e[p[i].lca].pb(i);
}
solve(1, 0);
printf("%d\n", d[1]);
}
return 0;
}

更新日志

  • 14199151 2015-07-27 15:26:38 Accepted 5293 1388MS 22824K 2513 B C++ SIO__Five