#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
int n, m, p[100010][20], d[100010], sub[100010], dp[100010];
pair<int,int> group[100010];
vector<int> edge[100010];
vector<pair<pair<int,int>,int>> add[100010];
vector<vector<int>> grp, ps, pss;
void dfs1(int u, int v, int depth) {
p[u][0] = v;
d[u] = depth;
sub[u] = 1;
for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
}
int lca(int u, int v) {
if (d[u] < d[v]) swap(u,v);
int i = 19;
while (i >= 0) {
if (d[p[u][i]] >= d[v]) u = p[u][i];
i--;
}
if (u == v) return u;
i = 19;
while (i >= 0) {
if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
i--;
}
return p[u][0];
}
void hld(int u, int v, int newgrp) {
if (newgrp) {
grp.push_back({u});
ps.push_back({0,0});
pss.push_back({0,0});
group[u] = {grp.size()-1,0};
} else {
grp[group[v].f].push_back(u);
ps[group[v].f].push_back(0);
pss[group[v].f].push_back(0);
group[u] = {group[v].f,group[v].s+1};
}
for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) hld(edge[u][i],u,(sub[edge[u][i]] <= (sub[u]-1)/2));
}
void dfs(int u, int v) {
for (int i = 0; i < edge[u].size(); i++) {
if (edge[u][i] != v) {
dfs(edge[u][i],u);
dp[u] += dp[edge[u][i]];
}
}
ps[group[u].f][group[u].s] = ps[group[u].f][group[u].s+1]+dp[u];
for (int i = 0; i < add[u].size(); i++) {
}
pss[group[u].f][group[u].s] = pss[group[u].f][group[u].s+1]+dp[u];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1,0,1);
cin >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add[lca(u,v)].push_back({{u,v},w});
}
hld(1,0,1);
/*for (int i = 0; i < grp.size(); i++) {
for (int j = 0; j < grp[i].size(); j++) cout << grp[i][j] << " ";
cout << endl;
}
for (int i = 1; i <= n; i++) cout << group[i].f << " " << group[i].s << endl;*/
}
Compilation message
election_campaign.cpp: In function 'void dfs1(int, int, int)':
election_campaign.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
| ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void hld(int, int, int)':
election_campaign.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) hld(edge[u][i],u,(sub[edge[u][i]] <= (sub[u]-1)/2));
| ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < edge[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
election_campaign.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < add[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
32108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
