#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
vector <int> gr[N];
int n, m;
vector <tuple<int, int, int>> vec;
int tin[N], tout[N], lc[17][N], sz[N];
int tiktak;
void dfs(int v, int pr) {
tin[v] = ++tiktak;
lc[0][v] = pr;
for (int i = 1; i < 17; i++) {
lc[i][v] = lc[i - 1][lc[i - 1][v]];
}
sz[v] = 1;
for (int to : gr[v]) {
if (to == pr) continue;
dfs(to, v);
sz[v] += sz[to];
}
tout[v] = ++tiktak;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 16; i >= 0; i--) {
if (!upper(lc[i][a], b)) a = lc[i][a];
}
return lc[0][a];
}
bool check(int i, int j) {
int a, b, c, d, val = 0;
tie(a, b) = make_tuple(get<0>(vec[i]), get<1>(vec[i]));
tie(c, d) = make_tuple(get<0>(vec[j]), get<1>(vec[j]));
int lc = lca(c, d);
if (upper(a, b)) {
val = (tin[a] <= tin[c] && tin[c] <= tin[b]);
val ^= (tin[a] <= tout[c] && tout[c] <= tin[b]);
if (val) return 0;
val = (tin[a] <= tin[d] && tin[d] <= tin[b]);
val ^= (tin[a] <= tout[d] && tout[d] <= tin[b]);
if (val) return 0;
val = (tin[a] <= tin[lc] && tin[lc] <= tin[b]);
val ^= (tin[a] <= tout[lc] && tout[lc] <= tin[b]);
if (val) return 0;
} else {
val = (tout[a] <= tin[c] && tin[c] <= tin[b]);
val ^= (tout[a] <= tout[c] && tout[c] <= tin[b]);
if (val) return 0;
val = (tout[a] <= tin[d] && tin[d] <= tin[b]);
val ^= (tout[a] <= tout[d] && tout[d] <= tin[b]);
if (val) return 0;
val = (tout[a] <= tin[lc] && tin[lc] <= tin[b]);
val ^= (tout[a] <= tout[lc] && tout[lc] <= tin[b]);
if (val) return 0;
int lc1 = lca(a, b);
if (lc1 == a || lc1 == b || lc1 == lc) return 0;
}
return 1;
}
int ans;
int solve1() {
for (int mask = 1; mask < (1 << m); mask++) {
vector <int> v;
for (int j = 0; j < m; j++) {
if ((mask >> j) & 1) {
v.push_back(j);
}
}
bool ok = 1;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v.size(); j++) {
if (i == j) continue;
ok &= check(v[i], v[j]);
}
}
if (ok) {
int res = 0;
for (int &to : v) {
res += get<2>(vec[to]);
}
ans = max(ans, res);
}
}
return ans;
}
int dp[N];
int solve2() {
sort(vec.begin(), vec.end());
int ptr = vec.size() - 1;
for (int i = n; i >= 1; i--) {
dp[i] = dp[i + 1];
while (ptr >= 0 && get<0>(vec[ptr]) == i) {
dp[i] = max(dp[i], dp[get<1>(vec[ptr]) + 1] + get<2>(vec[ptr]));
ptr--;
}
}
return dp[1];
}
vector <int> query[N];
int calc(int v, int id) {
int a, b;
tie(a, b) = make_tuple(get<0>(vec[id]), get<1>(vec[id]));
int res = 0;
while (a != v) {
for (int to : gr[a]) {
if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
res += dp[to];
}
a = lc[0][a];
}
while (b != v) {
for (int to : gr[b]) {
if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
res += dp[to];
}
b = lc[0][b];
}
for (int to : gr[v]) {
if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
res += dp[to];
}
return res;
}
void dfs1(int v, int pr) {
for (int to : gr[v]) {
if (to == pr) continue;
dfs1(to, v);
dp[v] += dp[to];
}
for (int id : query[v]) {
dp[v] = max(dp[v], calc(v, id) + get<2>(vec[id]));
}
}
int solve5() {
for (int i = 0; i < m; i++) {
query[lca(get<0>(vec[i]), get<1>(vec[i]))].push_back(i);
//cout << i << ": " << lca(get<0>(vec[i]), get<1>(vec[i])) << endl;
}
dfs1(1, 1);
return dp[1];
}
struct fen {
int tree[N + N];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val) {
while (pos < N + N) {
tree[pos] += val;
pos = pos | pos + 1;
}
}
int get(int r) {
int res = 0;
while (r >= 0) {
res += tree[r];
r = (r & r + 1) - 1;
}
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
fen tr;
int siz[N];
void dfs2(int v, int pr) {
for (int to : gr[v]) {
if (to == pr) continue;
dfs2(to, v);
siz[v] += siz[to];
}
int ok = -1;
for (int idd : query[v]) {
if (tr.get(tin[v], tin[get<0>(vec[idd])]) == 0 && tr.get(tin[v], tin[get<1>(vec[idd])]) == 0) {
ok = idd;
break;
}
}
if (ok != -1) {
siz[v]++;
tr.upd(tin[v], 1);
tr.upd(tout[v], -1);
}
}
main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
gr[u].push_back(v);
gr[v].push_back(u);
}
dfs(1, 1);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
if (tin[u] > tin[v]) swap(u, v);
vec.push_back({u, v, w});
}
if (m <= 15) {
printf("%d\n", solve1());
return 0;
}
if (gr[1][0] == 2 && (n == 2 || gr[n - 1][1] == n)) {
printf("%d\n", solve2());
return 0;
}
if (n <= 1000 && m <= 1000) {
printf("%d\n", solve5());
return 0;
}
for (int i = 0; i < m; i++) {
query[lca(get<0>(vec[i]), get<1>(vec[i]))].push_back(i);
}
dfs2(1, 1);
printf("%d\n", siz[1]);
}
Compilation message
election_campaign.cpp: In function 'int solve1()':
election_campaign.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
election_campaign.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); j++) {
~~^~~~~~~~~~
election_campaign.cpp: In member function 'void fen::upd(int, int)':
election_campaign.cpp:170:23: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
pos = pos | pos + 1;
~~~~^~~
election_campaign.cpp: In member function 'int fen::get(int)':
election_campaign.cpp:177:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
r = (r & r + 1) - 1;
~~^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:208:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:209:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
election_campaign.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
election_campaign.cpp:220:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5880 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
95 ms |
6008 KB |
Output is correct |
5 |
Correct |
584 ms |
16988 KB |
Output is correct |
6 |
Correct |
100 ms |
23008 KB |
Output is correct |
7 |
Correct |
257 ms |
20984 KB |
Output is correct |
8 |
Correct |
482 ms |
17528 KB |
Output is correct |
9 |
Correct |
330 ms |
19576 KB |
Output is correct |
10 |
Correct |
489 ms |
17272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5880 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
6008 KB |
Output is correct |
4 |
Correct |
118 ms |
24880 KB |
Output is correct |
5 |
Correct |
111 ms |
24808 KB |
Output is correct |
6 |
Correct |
109 ms |
24676 KB |
Output is correct |
7 |
Correct |
110 ms |
24912 KB |
Output is correct |
8 |
Correct |
110 ms |
24688 KB |
Output is correct |
9 |
Correct |
114 ms |
24808 KB |
Output is correct |
10 |
Correct |
113 ms |
24876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5880 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
6008 KB |
Output is correct |
4 |
Correct |
118 ms |
24880 KB |
Output is correct |
5 |
Correct |
111 ms |
24808 KB |
Output is correct |
6 |
Correct |
109 ms |
24676 KB |
Output is correct |
7 |
Correct |
110 ms |
24912 KB |
Output is correct |
8 |
Correct |
110 ms |
24688 KB |
Output is correct |
9 |
Correct |
114 ms |
24808 KB |
Output is correct |
10 |
Correct |
113 ms |
24876 KB |
Output is correct |
11 |
Correct |
18 ms |
6584 KB |
Output is correct |
12 |
Correct |
113 ms |
24796 KB |
Output is correct |
13 |
Correct |
113 ms |
24720 KB |
Output is correct |
14 |
Correct |
114 ms |
24772 KB |
Output is correct |
15 |
Correct |
114 ms |
24796 KB |
Output is correct |
16 |
Correct |
112 ms |
24644 KB |
Output is correct |
17 |
Correct |
113 ms |
24688 KB |
Output is correct |
18 |
Correct |
114 ms |
24760 KB |
Output is correct |
19 |
Correct |
113 ms |
24704 KB |
Output is correct |
20 |
Correct |
113 ms |
24796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
221 ms |
19052 KB |
Output is correct |
2 |
Correct |
111 ms |
27124 KB |
Output is correct |
3 |
Correct |
264 ms |
26576 KB |
Output is correct |
4 |
Correct |
186 ms |
21620 KB |
Output is correct |
5 |
Correct |
212 ms |
26344 KB |
Output is correct |
6 |
Correct |
186 ms |
21632 KB |
Output is correct |
7 |
Correct |
248 ms |
26088 KB |
Output is correct |
8 |
Correct |
217 ms |
21868 KB |
Output is correct |
9 |
Correct |
110 ms |
27336 KB |
Output is correct |
10 |
Correct |
258 ms |
25124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5880 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
95 ms |
6008 KB |
Output is correct |
5 |
Correct |
584 ms |
16988 KB |
Output is correct |
6 |
Correct |
100 ms |
23008 KB |
Output is correct |
7 |
Correct |
257 ms |
20984 KB |
Output is correct |
8 |
Correct |
482 ms |
17528 KB |
Output is correct |
9 |
Correct |
330 ms |
19576 KB |
Output is correct |
10 |
Correct |
489 ms |
17272 KB |
Output is correct |
11 |
Correct |
8 ms |
6008 KB |
Output is correct |
12 |
Correct |
8 ms |
6264 KB |
Output is correct |
13 |
Correct |
8 ms |
6008 KB |
Output is correct |
14 |
Correct |
8 ms |
6008 KB |
Output is correct |
15 |
Correct |
8 ms |
6008 KB |
Output is correct |
16 |
Correct |
8 ms |
6136 KB |
Output is correct |
17 |
Correct |
9 ms |
6008 KB |
Output is correct |
18 |
Correct |
10 ms |
6008 KB |
Output is correct |
19 |
Correct |
8 ms |
6008 KB |
Output is correct |
20 |
Correct |
8 ms |
6140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5880 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
95 ms |
6008 KB |
Output is correct |
5 |
Correct |
584 ms |
16988 KB |
Output is correct |
6 |
Correct |
100 ms |
23008 KB |
Output is correct |
7 |
Correct |
257 ms |
20984 KB |
Output is correct |
8 |
Correct |
482 ms |
17528 KB |
Output is correct |
9 |
Correct |
330 ms |
19576 KB |
Output is correct |
10 |
Correct |
489 ms |
17272 KB |
Output is correct |
11 |
Correct |
10 ms |
5880 KB |
Output is correct |
12 |
Correct |
7 ms |
5880 KB |
Output is correct |
13 |
Correct |
7 ms |
6008 KB |
Output is correct |
14 |
Correct |
118 ms |
24880 KB |
Output is correct |
15 |
Correct |
111 ms |
24808 KB |
Output is correct |
16 |
Correct |
109 ms |
24676 KB |
Output is correct |
17 |
Correct |
110 ms |
24912 KB |
Output is correct |
18 |
Correct |
110 ms |
24688 KB |
Output is correct |
19 |
Correct |
114 ms |
24808 KB |
Output is correct |
20 |
Correct |
113 ms |
24876 KB |
Output is correct |
21 |
Correct |
18 ms |
6584 KB |
Output is correct |
22 |
Correct |
113 ms |
24796 KB |
Output is correct |
23 |
Correct |
113 ms |
24720 KB |
Output is correct |
24 |
Correct |
114 ms |
24772 KB |
Output is correct |
25 |
Correct |
114 ms |
24796 KB |
Output is correct |
26 |
Correct |
112 ms |
24644 KB |
Output is correct |
27 |
Correct |
113 ms |
24688 KB |
Output is correct |
28 |
Correct |
114 ms |
24760 KB |
Output is correct |
29 |
Correct |
113 ms |
24704 KB |
Output is correct |
30 |
Correct |
113 ms |
24796 KB |
Output is correct |
31 |
Correct |
221 ms |
19052 KB |
Output is correct |
32 |
Correct |
111 ms |
27124 KB |
Output is correct |
33 |
Correct |
264 ms |
26576 KB |
Output is correct |
34 |
Correct |
186 ms |
21620 KB |
Output is correct |
35 |
Correct |
212 ms |
26344 KB |
Output is correct |
36 |
Correct |
186 ms |
21632 KB |
Output is correct |
37 |
Correct |
248 ms |
26088 KB |
Output is correct |
38 |
Correct |
217 ms |
21868 KB |
Output is correct |
39 |
Correct |
110 ms |
27336 KB |
Output is correct |
40 |
Correct |
258 ms |
25124 KB |
Output is correct |
41 |
Correct |
8 ms |
6008 KB |
Output is correct |
42 |
Correct |
8 ms |
6264 KB |
Output is correct |
43 |
Correct |
8 ms |
6008 KB |
Output is correct |
44 |
Correct |
8 ms |
6008 KB |
Output is correct |
45 |
Correct |
8 ms |
6008 KB |
Output is correct |
46 |
Correct |
8 ms |
6136 KB |
Output is correct |
47 |
Correct |
9 ms |
6008 KB |
Output is correct |
48 |
Correct |
10 ms |
6008 KB |
Output is correct |
49 |
Correct |
8 ms |
6008 KB |
Output is correct |
50 |
Correct |
8 ms |
6140 KB |
Output is correct |
51 |
Incorrect |
194 ms |
22224 KB |
Output isn't correct |
52 |
Halted |
0 ms |
0 KB |
- |