#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &pa) {
is >> pa.first >> pa.second;
return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
for (auto &v : vec) is >> v;
return is;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
os << "(" << pa.first << "," << pa.second << ")";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
os << "[";
for (auto v : vec) os << v << ",";
os << "]";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
os << "deq[";
for (auto v : vec) os << v << ",";
os << "]";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec) {
os << "{";
for (auto v : vec) os << v << ",";
os << "}";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec) {
os << "{";
for (auto v : vec) os << v << ",";
os << "}";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec) {
os << "{";
for (auto v : vec) os << v << ",";
os << "}";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) {
os << "{";
for (auto v : vec) os << v << ",";
os << "}";
return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {
os << "{";
for (auto v : mp) os << v.first << "=>" << v.second << ",";
os << "}";
return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
os << "{";
for (auto v : mp) os << v.first << "=>" << v.second << ",";
os << "}";
return os;
}
template <typename T>
void resize_array(vector<T> &vec, int len) {
vec.resize(len);
}
template <typename T, typename... Args>
void resize_array(vector<T> &vec, int len, Args... args) {
vec.resize(len);
for (auto &v : vec) resize_array(v, args...);
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) {
return make_pair(l.first + r.first, l.second + r.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) {
return make_pair(l.first - r.first, l.second - r.second);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
template <unsigned int MOD>
class ModInt {
public:
// static unsigned int MOD;
ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
explicit operator bool() const { return val != 0; }
ModInt operator-() const { return ModInt() - *this; }
ModInt operator+(const ModInt &r) const {
return ModInt().set_v(val + r.val);
}
ModInt operator-(const ModInt &r) const {
return ModInt().set_v(val + MOD - r.val);
}
ModInt operator*(const ModInt &r) const {
return ModInt().set_v(
(unsigned int)((unsigned long long)(val)*r.val % MOD));
}
ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
// ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return
// *this; }
unsigned int operator=(unsigned long long _v) {
set_v((_v % MOD + MOD));
return val;
}
bool operator==(const ModInt &r) const { return val == r.val; }
bool operator!=(const ModInt &r) const { return val != r.val; }
ModInt pow(long long n) const {
ModInt x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
ModInt inv() const { return pow(MOD - 2); }
unsigned int get_val() { return val; }
friend ostream &operator<<(ostream &os, const ModInt &r) {
return os << r.val;
}
friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
unsigned int val;
ModInt &set_v(unsigned int _v) {
val = (_v < MOD) ? _v : _v - MOD;
return *this;
}
};
constexpr unsigned int mod = 1e9 + 7;
using Mint = ModInt<mod>;
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) \
cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
// template<typename T>
class Tree { // 下标从0开始
struct LCA {
int node;
int son1 = -1, son2 = -1;
int dist = 0;
friend ostream &operator<<(ostream &os, const LCA &r) {
return os << r.node << "(" << r.son1 << ", " << r.son2 << ")";
}
};
public:
Tree(int node_num, int root) {
edges.resize(node_num);
size.resize(node_num);
weight.resize(node_num);
nth_son.resize(node_num);
centroid[0].resize(node_num, -1);
centroid[1].resize(node_num, -1);
this->root = root;
int bit_num = 1;
while ((1 << bit_num) < node_num) bit_num++;
parent.resize(node_num, vi(bit_num));
}
void AddEdge(int u, int v) {
edges[u].emplace_back(v);
edges[v].emplace_back(u);
}
void Dfs() {
function<void(int, int)> dfs = [&](int u, int p) {
size[u] = 1;
for (int i = 0; i < int(edges[u].size()); ++i) {
int v = edges[u][i];
if (v != p) {
parent[v][0] = u;
nth_son[v] = i;
dfs(v, u);
size[u] += size[v];
weight[u] = max(weight[u], size[v]);
}
}
centroid[0][u] = u;
for (int v : edges[u]) {
if (v == p) continue;
int cen = centroid[0][v];
while (cen != u) {
if (max(weight[cen], size[u] - size[cen]) <= size[u] / 2) {
centroid[0][u] = cen;
int fa_cen = parent[cen][0];
if (max(weight[fa_cen], size[u] - size[fa_cen]) <= size[u] / 2)
centroid[1][u] = fa_cen;
break;
}
else {
cen = parent[cen][0];
}
}
}
};
parent[root][0] = -1;
nth_son[root] = -1;
dfs(root, -1);
// O(nlogn)
for (int d = 1; d < int(parent[0].size()); ++d) {
for (int u = 0; u < int(parent.size()); ++u) {
if (parent[u][d - 1] == -1)
parent[u][d] = -1;
else
parent[u][d] = parent[parent[u][d - 1]][d - 1];
}
}
}
int GetDepth(int idx) {
int depth = 0;
int d = sz(parent[0]) - 1;
while (idx != root) {
if (parent[idx][d] != -1) {
depth |= (1 << d);
idx = parent[idx][d];
}
d--;
}
return depth;
};
// least common ancestor
LCA GetLca(int u, int v) {
int d1 = GetDepth(u);
int d2 = GetDepth(v);
if (d1 < d2) {
swap(u, v);
}
LCA lca;
int t = abs(d1 - d2);
if (t > 0) {
t--;
rep(i, 0, sz(parent[0])) {
if (t & (1 << i)) u = parent[u][i];
}
lca.son1 = nth_son[u];
u = parent[u][0];
}
if (u == v) {
lca.node = u;
lca.dist = abs(d1 - d2);
return lca;
}
int d = sz(parent[0]) - 1;
while (d >= 0) {
if (parent[u][d] != parent[v][d]) {
u = parent[u][d];
v = parent[v][d];
}
d--;
}
lca.son1 = nth_son[u];
lca.son2 = nth_son[v];
lca.node = parent[u][0];
lca.dist = d1 + d2 - 2 * GetDepth(lca.node);
return lca;
}
const vector<int>& GetCentroid(int idx) {
return centroid[idx];
}
const vector<vector<int>>& GetEdges() {
return edges;
}
const vector<vector<int>>& GetParent() {
return parent;
}
const vector<int>& GetNthSon() {
return nth_son;
}
private:
// nth_son[i] indicates which son of the father is i.
// nth_son[i] 表示i是父节点的第几个子节点
vector<int> nth_son;
vector<vector<int>> edges;
vector<vector<int>> parent;
vector<int> size; // size[i]表示以节点i为根的子树（整颗数以root为根）的节点个数，包括i节点本身
vector<int> weight; // weight[i]表示节点i的所有子树的节点数的最大值，包括向上的子树
vector<int> centroid[2]; //centroid[i]表示以节点i为根的子树（整颗数以root为根）的重心，重心最多有两个（质心）
int root = 0;
};
class Solution {
struct Edge {
int u, v;
int cost;
friend ostream &operator<<(ostream &os, const Edge &r) {
return os << r.u << "-->" << r.v << ":" << r.cost;
}
};
public:
void Solve() {
int n, m;
// n<=1000, m<=5000
while (cin >> n >> m) {
int total_cost = 0;
vi degree(n);
Tree tree(n, 0);
vector<Edge> edges;
int u, v, c;
rep(i, 0, m) {
cin >> u >> v >> c;
u--;
v--;
degree[u]++;
degree[v]++;
if (c == 0) {
tree.AddEdge(u, v);
} else {
edges.emplace_back(Edge{u, v, c});
total_cost += c;
}
}
tree.Dfs();
int max_degree = 1;
rep(i, 0, n) max_degree = *max_element(all(degree));
vector<Edge> even_edges;
for (auto edge : edges) {
// if (tree_path_len[edge.u][edge.v] % 2 == 0) {
if (tree.GetLca(edge.u, edge.v).dist % 2 == 0) {
even_edges.emplace_back(edge);
}
}
// O(mlogn)
vector<vi> node_to_even_edges(n);
vector<vector<pii>> node_to_direct_sons(n);
rep(i, 0, sz(even_edges)) {
// dbg(mp(even_edges[i].u, even_edges[i].v));
auto lca = tree.GetLca(even_edges[i].u, even_edges[i].v);
// dbg(lca);
node_to_even_edges[lca.node].emplace_back(i);
node_to_direct_sons[lca.node].emplace_back(mp(lca.son1, lca.son2));
}
// O(m*2^k)
vector<vi> dp(n, vi(1 << max_degree, -1));
vector<vi> cache(n, vi(n, -1));
const vector<vector<int>>& tree_edges = tree.GetEdges();
rep(i, 0, n) cache[i][i] = 0;
rep(u, 0, n) {
for (int v : tree_edges[u]) {
cache[u][v] = cache[v][u] = 0;
}
}
const vector<vi>& parent = tree.GetParent();
function<int(int, int)> get_most_cost = [&](int node, int mask) {
// dbg(mp(node, mask));
if (dp[node][mask] != -1) return dp[node][mask];
int cost = 0;
rep(i, 0, sz(tree_edges[node])) {
if ((1 << i) & mask) continue;
if (tree_edges[node][i] == parent[node][0]) continue;
cost += get_most_cost(tree_edges[node][i], 0);
}
dp[node][mask] = max(dp[node][mask], cost);
const vector<int>& nth_son = tree.GetNthSon();
rep(idx, 0, sz(node_to_even_edges[node])) {
int i = node_to_even_edges[node][idx];
if (node_to_direct_sons[node][idx].first != -1 &&
(mask & (1 << node_to_direct_sons[node][idx].first)))
continue;
if (node_to_direct_sons[node][idx].second != -1 &&
(mask & (1 << node_to_direct_sons[node][idx].second)))
continue;
cost = even_edges[i].cost;
int u = even_edges[i].u, v = even_edges[i].v;
if (u != node) cost += get_most_cost(u, 0);
if (v != node) cost += get_most_cost(v, 0);
vi nodes, subtree_cost;
while (true) {
if (cache[node][u] != -1) {
if (sz(nodes) > 0) {
cache[node][nodes.back()] =
subtree_cost.back() + cache[node][u];
per(i, 0, sz(nodes) - 1) {
cache[node][nodes[i]] =
subtree_cost[i] + cache[node][nodes[i + 1]];
}
}
break;
}
int p = parent[u][0];
nodes.emplace_back(u);
subtree_cost.emplace_back(get_most_cost(p, (1 << nth_son[u])));
u = p;
}
cost += cache[node][even_edges[i].u];
nodes.clear(), subtree_cost.clear();
while (true) {
if (cache[node][v] != -1) {
if (sz(nodes) > 0) {
cache[node][nodes.back()] =
subtree_cost.back() + cache[node][v];
per(i, 0, sz(nodes) - 1) {
cache[node][nodes[i]] =
subtree_cost[i] + cache[node][nodes[i + 1]];
}
}
break;
}
int p = parent[v][0];
nodes.emplace_back(v);
subtree_cost.emplace_back(get_most_cost(p, (1 << nth_son[v])));
v = p;
}
cost += cache[node][even_edges[i].v];
int mask2 = mask;
if (node_to_direct_sons[node][idx].first != -1)
mask2 |= (1 << node_to_direct_sons[node][idx].first);
if (node_to_direct_sons[node][idx].second != -1)
mask2 |= (1 << node_to_direct_sons[node][idx].second);
cost += get_most_cost(node, mask2);
dp[node][mask] = max(dp[node][mask], cost);
}
return dp[node][mask];
};
cout << total_cost - get_most_cost(0, 0) << endl;
}
}
private:
};
// #define USACO 1
void set_io(const string &name = "") {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#if FILE_IO || USACO
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
#endif
}
int main() {
#if USACO
set_io("time");
#else
set_io("input");
#endif
Solution().Solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9016 KB |
Output is correct |
| # |
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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2136 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
15 ms |
3420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
18 ms |
8892 KB |
Output is correct |
| 3 |
Correct |
8 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
21 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8920 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8980 KB |
Output is correct |
| 3 |
Correct |
8 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
15 ms |
8796 KB |
Output is correct |
