#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, in[N], out[N], timer, P[N][20], dp[N], fw[N], h[N];
vector<int> V[N];
vector<pair<pair<int,int>, int> > x[N];
void dfs0(int u, int p) {
in[u] = ++timer;
h[u] = h[p] + 1;
P[u][0] = p;
for(int i = 1; i <= 18; i++) P[u][i] = P[P[u][i - 1]][i - 1];
for(int i = 0; i < V[u].size(); i++) {
int v = V[u][i];
if(v != p) dfs0(v, u);
}
out[u] = timer;
}
bool check(int u, int v) {
return (in[u] <= in[v] && out[v] <= out[u]);
}
int lca(int u, int v) {
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = 18; i >= 0; i--) {
if(P[u][i] && !check(P[u][i], v)) u = P[u][i];
}
return P[u][0];
}
int n;
void upd(int id, int x) {
for(id; id <= n; id += id & (-id)) fw[id] += x;
}
int get(int id) {
int ans = 0;
for(id; id >= 1; id -= id & (-id)) ans += fw[id];
return ans;
}
int up(int u, int x) {
for(int i = 0; i <= 18; i++) {
if((1 << i) & x) u = P[u][i];
}
return u;
}
void dfs(int u, int p) {
int tot = 0;
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] != p) dfs(V[u][i], u), tot += dp[V[u][i]];
}
vector<vector<int>> bad;
bad.resize((int)x[u].size(), vector<int> ((int)x[u].size()));
for(int i = 0; i < (int)x[u].size(); i++) {
for(int j = 0; j < (int)x[u].size(); j++) {
if(i == j) continue;
bad[i][j] = (lca(x[u][i].f.f, x[u][j].f.f) != u || lca(x[u][i].f.f, x[u][j].f.s) != u ||
lca(x[u][i].f.s, x[u][j].f.f) != u || lca(x[u][i].f.s, x[u][j].f.s) != u );
}
}
dp[u] = 0;
for(int mask = 0; mask < (1 << (int)x[u].size()); mask++) {
vector<int> v;
int F = 0, cur = 0;
for(int i = 0; i < (int)x[u].size(); i++) {
if((1 << i) & mask) {
if(x[u][i].f.f != u)
v.push_back(x[u][i].f.f);
if(x[u][i].f.s != u)
v.push_back(x[u][i].f.s);
for(int j = 0; j < (int)x[u].size(); j++) {
if((1 << j) & mask) F |= bad[i][j];
}
cur += x[u][i].s;
}
}
if(F) continue;
cur += tot;
for(int i = 0; i < v.size(); i++) {
cur -= dp[up(v[i], h[v[i]] - h[u] - 1)];
cur += get(in[v[i]]);
}
dp[u] = max(dp[u], cur);
}
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] == p) continue;
upd(in[V[u][i]], tot - dp[V[u][i]]);
upd(out[V[u][i]] + 1, -(tot - dp[V[u][i]]));
}
upd(in[u], dp[u]);
upd(in[u] + 1, -dp[u]);
}
main(){
int m;
cin >> n >> m;
vector<pair<pair<int,int>, int> > e;
while(m--) {
int u, v, c;
cin >> u >> v >> c;
if(!c) V[u].push_back(v), V[v].push_back(u);
else {
e.push_back({{u, v}, c});
}
}
dfs0(1, 0);
int ans = 0, all = 0;
for(int i = 0; i < e.size(); i++) {
int u = e[i].f.f, v = e[i].f.s, c = e[i].s;
if((h[u] + h[v] - 2 * h[lca(u, v)]) % 2) {
ans += c; continue;
}
all += c;
x[lca(u, v)].push_back({{u, v}, c});
}
dfs(1, 0);
cout << all - dp[1] + ans;
}
Compilation message
training.cpp: In function 'void dfs0(long long int, long long int)':
training.cpp:16:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'void upd(long long int, long long int)':
training.cpp:36:9: warning: statement has no effect [-Wunused-value]
36 | for(id; id <= n; id += id & (-id)) fw[id] += x;
| ^~
training.cpp: In function 'long long int get(long long int)':
training.cpp:40:9: warning: statement has no effect [-Wunused-value]
40 | for(id; id >= 1; id -= id & (-id)) ans += fw[id];
| ^~
training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:83:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
training.cpp:89:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: At global scope:
training.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
97 | main(){
| ^~~~
training.cpp: In function 'int main()':
training.cpp:111:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0; i < e.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
11604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
9772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
9844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
9940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
10236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
10268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
10320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
