#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pf push_front
#define pb2 pop_back
#define pf2 pop_front
#define line printf("\n")
#define pq priority_queue
#define rep(k,i,j) for(int k = (int)i;k<(int)j;k++)
#define repd(k,i,j) for(int k = (int)i;k>=(int)j;k--)
#define ll long long
#define ALL(a) a.begin(),a.end()
#define vi vector<int>
using namespace std;
int INF = 1e9+7;
#define vvi vector<vi>
int N, M;
vi A, B, C;
vvi adj;
void read(int _N, int _M, vi U, vi V, vi _A, vi _B, vi _C) {
tie(N, M, A, B, C) = {_N, _M, _A, _B, _C};
adj.resize(N);
rep(k, 0, N - 1) {
U[k]--; V[k]--;
adj[U[k]].pb(V[k]);
adj[V[k]].pb(U[k]);
}
rep(k, 0, M) {
A[k]--; B[k]--;
}
}
void bfs(int u, int v, vi &path) {
vi par(N, -1);
queue<int> q;
q.push(u); par[u] = u;
while (q.size()) {
int a = q.front(); q.pop();
for (int b : adj[a]) if (par[b] == -1) {
q.push(b);
par[b] = a;
}
}
for (int b = v, a = par[v]; b != u; b = par[b], a = par[a]) {
path.pb(b);
}
path.pb(u);
}
vi par, hi;
void dfs(int a, int p) {
par[a] = p; hi[a] = hi[p] + 1;
for (int b : adj[a]) if (b != p) {
dfs(b, a);
}
}
void make_rooted_tree() { // root at 0
par = hi = vi(N);
dfs(0, 0);
}
vector<vvi> path;
vvi cost;
vi DP, SUM_CH;
int dp(int); int sum_ch(int);
int dp(int a) {
int &ret = DP[a];
if (ret != -1) return ret;
int sum = sum_ch(a);
ret = sum;
rep(k, 0, path[a].size()) {
int sum_ch_path = 0, c = cost[a][k];
for (int ch : path[a][k]) {
sum_ch_path += sum_ch(ch) - dp(ch);
}
int cur = sum + sum_ch_path + c;
ret = max(ret, cur);
}
return ret;
}
int sum_ch(int a) {
int &ret = SUM_CH[a];
if (ret != -1) return ret;
ret = 0;
for (auto b : adj[a]) ret += dp(b);
return ret;
}
int getMaximumVotes(int _N, int _M, vi _U, vi _V, vi _A, vi _B, vi _C) {
read(_N, _M, _U, _V, _A, _B, _C);
make_rooted_tree();
// puts("rooted tree");
path = vector<vvi>(N);
cost = vvi(N);
rep(k, 0, M) { // prepare
vi nodes; bfs(A[k], B[k], nodes);
int uv = A[k];
for (int a : nodes) // get lca
if (hi[uv] > hi[a])
uv = a;
vi nodes_wo_lca;
for (int a : nodes) if(a != uv)
nodes_wo_lca.pb(a);
path[uv].pb(nodes_wo_lca);
cost[uv].pb(C[k]);
}
adj = vvi(N);
rep(k, 1, N) adj[par[k]].pb(k);
// puts("prepare");
DP = SUM_CH = vi(N, -1);
return dp(0);
}
// grader.cpp
#include <stdio.h>
#include <vector>
int main() {
int N, M;
std::vector<int> U, V;
std::vector<int> A, B, C;
scanf("%d", &N);
U.resize(N-1); V.resize(N-1);
A.resize(M); B.resize(M); C.resize(M);
for (int i = 0 ; i < N-1 ; i++) {
scanf("%d %d", &U[i], &V[i]);
}
scanf("%d", &M);
for (int i = 0 ; i < M ; i++) {
scanf("%d %d %d", &A[i], &B[i], &C[i]);
}
int ans = getMaximumVotes(N, M, U, V, A, B, C);
printf("%d\n", ans);
return 0;
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
election_campaign.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &U[i], &V[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
~~~~~^~~~~~~~~~
election_campaign.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
28 ms |
2680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |