// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int LOG = 17;
struct SegmentTree
{
private:
int treeSize;
vector<int> nodes;
void initTree(int id, int low, int high)
{
if (low == high)
{
nodes[id] = 0;
return;
}
int mid = (low + high) / 2;
initTree(id * 2, low, mid);
initTree(id * 2 + 1, mid + 1, high);
}
void update(int id, int low, int high, int left, int right, int val)
{
if (low > right || high < left)
{
return;
}
if (low >= left && high <= right)
{
nodes[id] += val;
return;
}
int mid = (low + high) / 2;
update(id * 2, low, mid, left, right, val);
update(id * 2 + 1, mid + 1, high, left, right, val);
}
int get(int id, int low, int high, int pos)
{
if (low > pos || high < pos)
{
return 0;
}
if (low == high)
{
return nodes[id];
}
int mid = (low + high) / 2;
return nodes[id] + (pos <= mid ? get(id * 2, low, mid, pos) : get(id * 2 + 1, mid + 1, high, pos));
}
public:
void init(int treeSize)
{
this->treeSize = treeSize;
int tmp = 1;
while (tmp < treeSize)
{
tmp *= 2;
}
nodes.resize(tmp * 2);
initTree(1, 1, treeSize);
}
void update(int left, int right, int val)
{
update(1, 1, treeSize, left, right, val);
}
int get(int pos)
{
return get(1, 1, treeSize, pos);
}
} smt;
struct Plan
{
int u, v, cost;
} plans[MAX_N];
int numCity, numPLan;
vector<int> adj[MAX_N], planAt[MAX_N];
int start[MAX_N], stop[MAX_N], depth[MAX_N];
int parent[MAX_N][LOG];
int id;
int f[MAX_N], sumF[MAX_N];
void dfs(int node)
{
for (int level = 0; level < LOG - 1; level++)
{
parent[node][level + 1] = parent[parent[node][level]][level];
}
start[node] = ++id;
for (auto &u : adj[node])
{
if (u != parent[node][0])
{
depth[u] = depth[node] + 1;
parent[u][0] = node;
dfs(u);
}
}
stop[node] = id;
}
int lca(int u, int v)
{
if (depth[u] >depth[v])
{
swap(u, v);
}
for (int level = LOG - 1; level >= 0; level--)
{
if (depth[parent[v][level]] >= depth[u])
{
v = parent[v][level];
}
}
if (u == v){
return u;
}
for (int level = LOG - 1; level >= 0; level--)
{
if (parent[u][level] != parent[v][level])
{
u = parent[u][level];
v = parent[v][level];
}
}
return parent[u][0];
}
int jump(int node, int high)
{
for (int level = LOG - 1; level >= 0; level--)
{
if (depth[parent[node][level]] >= high)
{
node = parent[node][level];
}
}
return node;
}
void dp(int node)
{
sumF[node] = 0;
for (auto &u : adj[node])
{
if (u != parent[node][0])
{
dp(u);
sumF[node] += f[u];
}
}
f[node] = sumF[node];
for (auto &index : planAt[node])
{
int u = plans[index].u, v = plans[index].v;
int pu = jump(u, depth[node] + 1), pv = jump(v, depth[node] + 1);
int tmp = sumF[node];
if (u != node){
tmp += smt.get(start[u]) - f[pu];
}
if (v != node)
{
tmp += smt.get(start[v]) - f[pv];
}
f[node] = max(f[node], tmp + plans[index].cost);
}
for (auto &u : adj[node])
{
if (u != parent[node][0])
{
smt.update(start[u], stop[u], sumF[node] - f[u]);
}
}
smt.update(start[node], start[node], sumF[node]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
cin >> numCity;
for (int i = 1; i < numCity; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> numPLan;
for (int i = 1; i <= numPLan; i++)
{
cin >> plans[i].u >> plans[i].v >> plans[i].cost;
}
depth[0] = -1;
id = 0;
dfs(1);
smt.init(numCity);
for (int i = 1; i <= numPLan; i++)
{
planAt[lca(plans[i].u, plans[i].v)].push_back(i);
}
dp(1);
cout << f[1];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
5164 KB |
Output is correct |
5 |
Correct |
115 ms |
18988 KB |
Output is correct |
6 |
Correct |
65 ms |
32932 KB |
Output is correct |
7 |
Correct |
123 ms |
28060 KB |
Output is correct |
8 |
Correct |
79 ms |
19372 KB |
Output is correct |
9 |
Correct |
110 ms |
25244 KB |
Output is correct |
10 |
Correct |
94 ms |
19428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5296 KB |
Output is correct |
4 |
Correct |
156 ms |
36496 KB |
Output is correct |
5 |
Correct |
152 ms |
36480 KB |
Output is correct |
6 |
Correct |
164 ms |
36620 KB |
Output is correct |
7 |
Correct |
155 ms |
36580 KB |
Output is correct |
8 |
Correct |
148 ms |
36524 KB |
Output is correct |
9 |
Correct |
151 ms |
36560 KB |
Output is correct |
10 |
Correct |
187 ms |
36564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5296 KB |
Output is correct |
4 |
Correct |
156 ms |
36496 KB |
Output is correct |
5 |
Correct |
152 ms |
36480 KB |
Output is correct |
6 |
Correct |
164 ms |
36620 KB |
Output is correct |
7 |
Correct |
155 ms |
36580 KB |
Output is correct |
8 |
Correct |
148 ms |
36524 KB |
Output is correct |
9 |
Correct |
151 ms |
36560 KB |
Output is correct |
10 |
Correct |
187 ms |
36564 KB |
Output is correct |
11 |
Correct |
15 ms |
6092 KB |
Output is correct |
12 |
Correct |
161 ms |
36776 KB |
Output is correct |
13 |
Correct |
162 ms |
36772 KB |
Output is correct |
14 |
Correct |
161 ms |
36940 KB |
Output is correct |
15 |
Correct |
161 ms |
36832 KB |
Output is correct |
16 |
Correct |
143 ms |
36888 KB |
Output is correct |
17 |
Correct |
167 ms |
36808 KB |
Output is correct |
18 |
Correct |
177 ms |
37072 KB |
Output is correct |
19 |
Correct |
141 ms |
36884 KB |
Output is correct |
20 |
Correct |
149 ms |
36816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
22024 KB |
Output is correct |
2 |
Correct |
140 ms |
36580 KB |
Output is correct |
3 |
Correct |
267 ms |
31104 KB |
Output is correct |
4 |
Correct |
176 ms |
22356 KB |
Output is correct |
5 |
Correct |
229 ms |
30252 KB |
Output is correct |
6 |
Correct |
161 ms |
22512 KB |
Output is correct |
7 |
Correct |
291 ms |
29952 KB |
Output is correct |
8 |
Correct |
189 ms |
22444 KB |
Output is correct |
9 |
Correct |
145 ms |
36588 KB |
Output is correct |
10 |
Correct |
312 ms |
28340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
5164 KB |
Output is correct |
5 |
Correct |
115 ms |
18988 KB |
Output is correct |
6 |
Correct |
65 ms |
32932 KB |
Output is correct |
7 |
Correct |
123 ms |
28060 KB |
Output is correct |
8 |
Correct |
79 ms |
19372 KB |
Output is correct |
9 |
Correct |
110 ms |
25244 KB |
Output is correct |
10 |
Correct |
94 ms |
19428 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
4 ms |
5332 KB |
Output is correct |
13 |
Correct |
5 ms |
5296 KB |
Output is correct |
14 |
Correct |
4 ms |
5176 KB |
Output is correct |
15 |
Correct |
4 ms |
5204 KB |
Output is correct |
16 |
Correct |
4 ms |
5172 KB |
Output is correct |
17 |
Correct |
5 ms |
5168 KB |
Output is correct |
18 |
Correct |
5 ms |
5340 KB |
Output is correct |
19 |
Correct |
4 ms |
5204 KB |
Output is correct |
20 |
Correct |
4 ms |
5332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
5164 KB |
Output is correct |
5 |
Correct |
115 ms |
18988 KB |
Output is correct |
6 |
Correct |
65 ms |
32932 KB |
Output is correct |
7 |
Correct |
123 ms |
28060 KB |
Output is correct |
8 |
Correct |
79 ms |
19372 KB |
Output is correct |
9 |
Correct |
110 ms |
25244 KB |
Output is correct |
10 |
Correct |
94 ms |
19428 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
4 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5296 KB |
Output is correct |
14 |
Correct |
156 ms |
36496 KB |
Output is correct |
15 |
Correct |
152 ms |
36480 KB |
Output is correct |
16 |
Correct |
164 ms |
36620 KB |
Output is correct |
17 |
Correct |
155 ms |
36580 KB |
Output is correct |
18 |
Correct |
148 ms |
36524 KB |
Output is correct |
19 |
Correct |
151 ms |
36560 KB |
Output is correct |
20 |
Correct |
187 ms |
36564 KB |
Output is correct |
21 |
Correct |
15 ms |
6092 KB |
Output is correct |
22 |
Correct |
161 ms |
36776 KB |
Output is correct |
23 |
Correct |
162 ms |
36772 KB |
Output is correct |
24 |
Correct |
161 ms |
36940 KB |
Output is correct |
25 |
Correct |
161 ms |
36832 KB |
Output is correct |
26 |
Correct |
143 ms |
36888 KB |
Output is correct |
27 |
Correct |
167 ms |
36808 KB |
Output is correct |
28 |
Correct |
177 ms |
37072 KB |
Output is correct |
29 |
Correct |
141 ms |
36884 KB |
Output is correct |
30 |
Correct |
149 ms |
36816 KB |
Output is correct |
31 |
Correct |
213 ms |
22024 KB |
Output is correct |
32 |
Correct |
140 ms |
36580 KB |
Output is correct |
33 |
Correct |
267 ms |
31104 KB |
Output is correct |
34 |
Correct |
176 ms |
22356 KB |
Output is correct |
35 |
Correct |
229 ms |
30252 KB |
Output is correct |
36 |
Correct |
161 ms |
22512 KB |
Output is correct |
37 |
Correct |
291 ms |
29952 KB |
Output is correct |
38 |
Correct |
189 ms |
22444 KB |
Output is correct |
39 |
Correct |
145 ms |
36588 KB |
Output is correct |
40 |
Correct |
312 ms |
28340 KB |
Output is correct |
41 |
Correct |
4 ms |
5204 KB |
Output is correct |
42 |
Correct |
4 ms |
5332 KB |
Output is correct |
43 |
Correct |
5 ms |
5296 KB |
Output is correct |
44 |
Correct |
4 ms |
5176 KB |
Output is correct |
45 |
Correct |
4 ms |
5204 KB |
Output is correct |
46 |
Correct |
4 ms |
5172 KB |
Output is correct |
47 |
Correct |
5 ms |
5168 KB |
Output is correct |
48 |
Correct |
5 ms |
5340 KB |
Output is correct |
49 |
Correct |
4 ms |
5204 KB |
Output is correct |
50 |
Correct |
4 ms |
5332 KB |
Output is correct |
51 |
Correct |
210 ms |
22888 KB |
Output is correct |
52 |
Correct |
177 ms |
36820 KB |
Output is correct |
53 |
Correct |
269 ms |
28748 KB |
Output is correct |
54 |
Correct |
164 ms |
22852 KB |
Output is correct |
55 |
Correct |
216 ms |
22344 KB |
Output is correct |
56 |
Correct |
148 ms |
36776 KB |
Output is correct |
57 |
Correct |
237 ms |
29772 KB |
Output is correct |
58 |
Correct |
174 ms |
22776 KB |
Output is correct |
59 |
Correct |
198 ms |
22800 KB |
Output is correct |
60 |
Correct |
161 ms |
36824 KB |
Output is correct |
61 |
Correct |
268 ms |
29948 KB |
Output is correct |
62 |
Correct |
171 ms |
22612 KB |
Output is correct |
63 |
Correct |
216 ms |
22368 KB |
Output is correct |
64 |
Correct |
171 ms |
36796 KB |
Output is correct |
65 |
Correct |
278 ms |
29800 KB |
Output is correct |
66 |
Correct |
177 ms |
22736 KB |
Output is correct |
67 |
Correct |
196 ms |
22492 KB |
Output is correct |
68 |
Correct |
151 ms |
36820 KB |
Output is correct |
69 |
Correct |
245 ms |
27852 KB |
Output is correct |
70 |
Correct |
161 ms |
22804 KB |
Output is correct |