#include <bits/stdc++.h>
#define int long long
#define sz(x) (int)(x.size())
using namespace std;
const int LOG=10;
int n, k, m;
//LSONE
int LSOne(int i) {
return i&(-i);
}
//LCA
vector<vector<int>> child;
vector<vector<int>> up;
vector<int> depth;
void dfs(int s, int last=-1) {
for (auto u: child[s]) {
if (u==last) continue;
depth[u]=depth[s]+1;
up[u][0]=s;
for (int i=1; i<LOG; i++) {
up[u][i]=up[ up[u][i-1] ][ i-1 ];
}
dfs(u, s);
}
}
int getlca(int a, int b) {
if (a==b) return a;
if (depth[a] < depth[b]) swap(a, b);
int k = depth[a] - depth[b];
for (int j = LOG-1; j >= 0; j--) {
if (k & (1<<j)) {
a=up[a][j];
}
}
if (a==b) return a;
for (int j = LOG-1; j >= 0; j--) {
if (up[a][j] != up[b][j]) {
a=up[a][j];
b=up[b][j];
}
}
return up[a][0];
}
//DP
vector<vector<int>> memo;
vector<vector<pair<pair<int, int>, int>>> adj;
vector<vector<pair<int, int>>> passepar;
vector<vector<int>> memo2;
int dp(int s, int mask) {
if (__builtin_popcount(mask)>=child[s].size()) return 0;
if (memo[s][mask]!=-1) return memo[s][mask];
int ans=0;
for (auto u: child[s]) {
ans=max(ans, dp(u, 0));
}
for (auto u: adj[s]) {
int a=u.first.first, b=u.first.second, c=u.second;
int temp=mask;
bool flag=false;
while (temp>0) {
int lsone=LSOne(temp);
if (passepar[a][b].first==child[s][log2(lsone)]) flag=true;
if (passepar[a][b].second==child[s][log2(lsone)]) flag=true;
temp-=lsone;
}
if (flag) continue;
if (memo2[a][b]!=-1) {
ans=max(ans, memo2[a][b]);
continue;
}
int sum=0;
int aa=a, bb=b;
if (a!=s) sum+=dp(a, 0);
int tempmask=mask;
while (a!=s) {
int prec=a;
a=up[a][0];
int bitmask=0;
for (int i=0; i<sz(child[a]); i++) {
if (child[a][i]==prec || child[a][i]==b) {
bitmask+=(1<<i);
}
}
if (a==s) tempmask|=bitmask;
else sum+=dp(a, bitmask);
}
if (b!=s) sum+=dp(b, 0);
while (b!=s) {
int prec=b;
b=up[b][0];
int bitmask=0;
for (int i=0; i<sz(child[b]); i++) {
if (child[b][i]==prec) {
bitmask+=(1<<i);
}
}
if (a==s) bitmask|=tempmask;
sum+=dp(b, bitmask);
}
memo2[a][b]=sum+c;
ans=max(ans, sum+c);
}
return memo[s][mask]=ans;
}
void solve() {
cin >> n >> m;
memo.clear();
memo.resize(n, vector<int>(1<<10, -1));
memo2.clear();
memo2.resize(n, vector<int>(n, -1));
passepar.clear();
passepar.resize(n, vector<pair<int, int>>(n));
adj.clear();
adj.resize(n);
child.clear();
child.resize(n);
up.clear();
up.resize(n, vector<int>(LOG));
depth.clear();
depth.resize(n);
vector<pair<pair<int, int>, int>> temp;
for (int i=0; i<m; i++) {
int u, v, c; cin >> u >> v >> c;
u--, v--;
if (c==0) {
child[u].push_back(v);
child[v].push_back(u);
} else {
temp.push_back({{u, v}, c});
}
}
depth[0]=0;
dfs(0);
for (int s=0; s<n; s++) {
for (int i=0; i<sz(child[s]); i++) {
auto u=child[s][i];
if (u==up[s][0]) {
child[s].erase(child[s].begin()+i);
}
}
}
int ans=0;
for (int i=n-1; i<m; i++) {
int u=temp[i-n+1].first.first, v=temp[i-n+1].first.second;
int c=temp[i-n+1].second;
int lca=getlca(u, v);
if (u!=v && (depth[u]+depth[v]-2*depth[lca])%2==0) {
adj[lca].push_back({{u, v}, c});
int a=-1, b=-1;
for (auto s: child[lca]) {
if (depth[s]<depth[lca]) continue;
if (getlca(s, u)==s) {
if (a==-1) a=s;
else b=s;
}
if (getlca(s, v)==s) {
if (a==-1) a=s;
else b=s;
}
}
passepar[u][v]={a, b};
}
ans+=c;
}
cout << ans-dp(0, 0) << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
return 0;
}
Compilation message
training.cpp: In function 'long long int dp(long long int, long long int)':
training.cpp:87:13: warning: unused variable 'aa' [-Wunused-variable]
87 | int aa=a, bb=b;
| ^~
training.cpp:87:19: warning: unused variable 'bb' [-Wunused-variable]
87 | int aa=a, bb=b;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
32344 KB |
Output is correct |
| 2 |
Correct |
17 ms |
32580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
32348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
10332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
32344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
