Advertisement
Guest User

Untitled

a guest
May 26th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define st first
  5. #define nd second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define cl(x, v) memset((x), (v), sizeof(x))
  9. #define db(x) cerr << #x << " == " << x << endl
  10. #define dbs(x) cerr << x << endl
  11. #define _ << ", " <<
  12. #define gcd(x, y) __gcd((x), (y))
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16. typedef pair<int, int> pii;
  17. typedef pair<int, pii> piii;
  18. typedef pair<ll, ll> pll;
  19. typedef vector<int> vi;
  20. typedef vector<vi> vii;
  21.  
  22. const ld EPS = 1e-9, PI = acos(-1.);
  23. const ll LINF = 0x3f3f3f3f3f3f3f3f, LMOD = 1011112131415161719ll;
  24. const int INF = 0x3f3f3f3f, MOD = 1e9+7;
  25. const int N = 5e3+5;
  26. const int K = 20;
  27. const int M = K+5;
  28.  
  29. vi adj[N];
  30. int vis[N], h[N], anc[N][M];
  31. int n, d, a, b, w, m;
  32. ll wei[N], sum[N], dp[N];
  33.  
  34. void dfs (int u) {
  35.     vis[u] = 1;
  36.     for (auto v : adj[u]) if (!vis[v]) {
  37.         h[v] = h[u]+1;
  38.         anc[v][0] = u;
  39.         dfs(v);
  40.     }
  41. }
  42.  
  43. void dfstwo (int u) {
  44.     vis[u] = 1;
  45.     for (auto v : adj[u]) if (!vis[v]) {
  46.         dfstwo(v);
  47.         sum[u] += sum[v];
  48.     }
  49. }
  50.  
  51. void build () {
  52.     anc[1][0] = 1;
  53.     dfs(1);
  54.     for (int j = 1; j <= K; j++) for (int i = 1; i <= n; i++)
  55.         anc[i][j] = anc[anc[i][j-1]][j-1];
  56. }
  57.  
  58. int lca (int u, int v) {
  59.     if (h[u] < h[v]) swap(u, v);
  60.     for (int j = 20; j >= 0; j--) if (h[anc[u][j]] >= h[v]) u = anc[u][j];
  61.     if (u == v) return u;
  62.     for (int j = 20; j >= 0; j--) if (anc[u][j] != anc[v][j]) u = anc[u][j], v = anc[v][j];
  63.     return anc[u][0];
  64. }
  65.  
  66.  
  67. int main () {
  68.     scanf("%d%d", &n, &d);
  69.  
  70.     for (int i = 0; i < n-1; i++) {
  71.         scanf("%d%d", &a, &b);
  72.         adj[a].pb(b);
  73.         adj[b].pb(a);
  74.     }
  75.  
  76.     build();
  77.  
  78.     scanf("%d", &m);
  79.     for (int i = 1; i <= m; i++) {
  80.         scanf("%d%d", &a, &b);
  81.         wei[a] = b;
  82.     }
  83.  
  84.     scanf("%d", &m);
  85.     while (m--) {
  86.         scanf("%d%d%d", &a, &b, &w);
  87.         sum[a] += w;
  88.         sum[b] += w;
  89.         sum[lca(a, b)] -= w;
  90.     }
  91.  
  92.     cl(vis, 0);
  93.     dfstwo(1);
  94.  
  95.     db(sum[4]);
  96.     db(sum[6]);
  97.     for (int i = 1; i <= n; i++) if (wei[i]) {
  98.         for (int j = N-1; j >= wei[i]; j--) {
  99.             dp[j] = max(dp[j], dp[j-wei[i]] + sum[i]);
  100.         }
  101.     }
  102.  
  103.     for (int i = 1; i <= n; i++) printf("sum[%d] = %lld\n", i, sum[i]);
  104.  
  105.     ll ans = 0;
  106.     for (int i = 0; i <= d; i++) {
  107.         ans = max(ans, dp[i]);
  108.         printf("dp[%d] = %lld\n", i, dp[i]);
  109.     }
  110.  
  111.     printf("%lld\n", ans);
  112.  
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement