#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define u128 unsigned __int128
#define i128 __int128
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define ff first
#define ss second
const ll inf = 9e18;
const int iinf = 2e9;
const int N = 1e5;
const ll MOD = 1e9 + 7;
vector<vector<int>> g;
vector<vector<int>> up;
vector<int> depth, ord;
int logn;
void dfs(int v, int p){
up[v].assign(logn + 1, 1);
up[v][0] = p;
for (int i = 1; i <= logn; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto to : g[v]){
if (to != p){
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
ord.pb(v);
}
int lca(int u, int v){
if (depth[u] < depth[v])
swap(u, v);
int dlt = depth[u] - depth[v];
for (int k = logn; k > -1; --k)
if ((1 << k) & dlt)
u = up[u][k];
if (u == v)
return u;
for (int k = logn; k > -1; --k){
int nu = up[u][k], nv = up[v][k];
if (nu != nv){
u = nu;
v = nv;
}
}
return up[u][0];
}
void solution(){
int n;
cin >> n;
g.resize(n + 1);
up.resize(n + 1);
depth.assign(n + 1, 0);
logn = ceil(log2(n));
bool case23 = true;
bool case4 = true;
for (int i = 0; i < n - 1; ++i){
int x, y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
case23 &= (abs(x - y) == 1);
}
int m;
cin >> m;
vector<pair<int, int>> v(m);
vector<int> c(m);
for (int i = 0; i < m; ++i){
cin >> v[i].ff >> v[i].ss >> c[i];
if (v[i].ff > v[i].ss)
swap(v[i].ff, v[i].ss);
case4 &= (c[i] == 1);
}
if (case23){
vector<pair<int, int>> vn(m);
vector<int> order(m), cn(m);
iota(all(order), 0);
sort(all(order), [&](int i, int j){
return v[i].ss < v[j].ss;
});
for (int i = 0; i < m; ++i){
vn[i] = v[order[i]];
cn[i] = c[order[i]];
}
vector<int> vr(m);
for (int i = 0; i < m; ++i)
vr[i] = vn[i].ss;
vector<ll> dp(m, 0);
for (int i = 0; i < m; ++i){
int l = vn[i].ff, r = vn[i].ss;
int idx = int(upper_bound(all(vr), l - 1) - vr.begin() - 1);
dp[i] = max((i == 0 ? 0 : dp[i - 1]), (idx == -1 ? 0 : dp[idx]) + cn[i]);
}
cout << dp[m - 1];
} else if (m <= 15){
dfs(1, 1);
vector<vector<int>> el(m);
for (int i = 0; i < m; ++i){
int a = v[i].ff, b = v[i].ss;
int lc = lca(a, b);
while (a != lc){
el[i].pb(a);
a = up[a][0];
}
el[i].pb(lc);
while (b != lc){
el[i].pb(b);
b = up[b][0];
}
}
vector<vector<bool>> can(m, vector<bool>(m, false));
for (int i = 0; i < m; ++i){
for (int j = i + 1; j < m; ++j){
vector<int> used(n + 1, 0);
for (int k = 0; k < sz(el[i]); ++k)
used[el[i][k]] = 1;
bool ok = true;
for (int k = 0; k < sz(el[j]) && ok; ++k)
if (used[el[j][k]])
ok = false;
can[i][j] = ok;
}
}
int M = (1 << m) - 1;
ll ans = 0;
for (int k = 0; k <= M; ++k){
vector<int> bits;
for (int i = 0; (1 << i) <= k; ++i)
if ((1 << i) & k)
bits.pb(i);
bool ok = true;
for (int i = 0; i < sz(bits) && ok; ++i)
for (int j = i + 1; j < sz(bits) && ok; ++j)
if (!can[bits[i]][bits[j]])
ok = false;
if (!ok)
continue;
ll curr = 0;
for (int i : bits)
curr += c[i];
ans = max(ans, curr);
}
cout << ans;
} else if (n <= 1000 && m <= 1000){
vector<vector<tuple<int, int, int>>> p(n + 1);
vector<ll> dp(n + 1, 0);
dfs(1, 1);
for (int i = 0; i < m; ++i){
int l = lca(v[i].ff, v[i].ss);
p[l].pb(mt(v[i].ff, v[i].ss, c[i]));
}
for (int vert : ord){
ll base = 0;
for (auto to : g[vert])
if (to != up[vert][0])
base += dp[to];
dp[vert] = base;
for (auto [l, r, cost] : p[vert]){
ll otn = 0;
while (l != vert){
otn += dp[l];
l = up[l][0];
}
while (r != vert){
otn += dp[r];
r = up[r][0];
}
dp[vert] = max(dp[vert], base - otn + cost);
}
}
cout << dp[1];
} else if (case4){
} else{
}
}
signed main(/* Kurmankul Nurislam */){
//freopen("fcolor.in", "r", stdin);
//freopen("fcolor.out", "w", stdout);
cin.tie(nullptr) -> sync_with_stdio(false);
int t = 1;
//cin >> t;
while (t--){
solution();
//cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |