Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define st first
- #define nd second
- #define mp make_pair
- #define pb push_back
- #define cl(x, v) memset((x), (v), sizeof(x))
- #define db(x) cerr << #x << " == " << x << endl
- #define dbs(x) cerr << x << endl
- #define _ << ", " <<
- #define gcd(x, y) __gcd((x), (y))
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<int, pii> piii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<vi> vii;
- const ld EPS = 1e-9, PI = acos(-1.);
- const ll LINF = 0x3f3f3f3f3f3f3f3f, LMOD = 1011112131415161719ll;
- const int INF = 0x3f3f3f3f, MOD = 1e9+7;
- const int N = 5e3+5;
- const int K = 20;
- const int M = K+5;
- vi adj[N];
- int vis[N], h[N], anc[N][M];
- int n, d, a, b, w, m;
- ll wei[N], sum[N], dp[N];
- void dfs (int u) {
- vis[u] = 1;
- for (auto v : adj[u]) if (!vis[v]) {
- h[v] = h[u]+1;
- anc[v][0] = u;
- dfs(v);
- }
- }
- void dfstwo (int u) {
- vis[u] = 1;
- for (auto v : adj[u]) if (!vis[v]) {
- dfstwo(v);
- sum[u] += sum[v];
- }
- }
- void build () {
- anc[1][0] = 1;
- dfs(1);
- for (int j = 1; j <= K; j++) for (int i = 1; i <= n; i++)
- anc[i][j] = anc[anc[i][j-1]][j-1];
- }
- int lca (int u, int v) {
- if (h[u] < h[v]) swap(u, v);
- for (int j = 20; j >= 0; j--) if (h[anc[u][j]] >= h[v]) u = anc[u][j];
- if (u == v) return u;
- for (int j = 20; j >= 0; j--) if (anc[u][j] != anc[v][j]) u = anc[u][j], v = anc[v][j];
- return anc[u][0];
- }
- int main () {
- scanf("%d%d", &n, &d);
- for (int i = 0; i < n-1; i++) {
- scanf("%d%d", &a, &b);
- adj[a].pb(b);
- adj[b].pb(a);
- }
- build();
- scanf("%d", &m);
- for (int i = 1; i <= m; i++) {
- scanf("%d%d", &a, &b);
- wei[a] = b;
- }
- scanf("%d", &m);
- while (m--) {
- scanf("%d%d%d", &a, &b, &w);
- sum[a] += w;
- sum[b] += w;
- sum[lca(a, b)] -= w;
- }
- cl(vis, 0);
- dfstwo(1);
- db(sum[4]);
- db(sum[6]);
- for (int i = 1; i <= n; i++) if (wei[i]) {
- for (int j = N-1; j >= wei[i]; j--) {
- dp[j] = max(dp[j], dp[j-wei[i]] + sum[i]);
- }
- }
- for (int i = 1; i <= n; i++) printf("sum[%d] = %lld\n", i, sum[i]);
- ll ans = 0;
- for (int i = 0; i <= d; i++) {
- ans = max(ans, dp[i]);
- printf("dp[%d] = %lld\n", i, dp[i]);
- }
- printf("%lld\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement