Advertisement
konchin_shih

b322

Feb 5th, 2021
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include"./template/headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. inline void solve() {
  14.     int n, m;
  15.     while (cin >> n >> m) {
  16.         V<V<int>> edge(n);
  17.         for (int i = 1; i < n; i++) {
  18.             static int a, b; cin >> a >> b;
  19.             edge[a].emplace_back(b);
  20.             edge[b].emplace_back(a);
  21.         }
  22.         V<V<int>> anc(n, V<int>(__lg(n) + 1));
  23.         V<int> tin(n), tout(n);
  24.         F<void(int, int)> build = [&](int cur, int pre) {
  25.             static int t = 0;
  26.             tin[cur] = t++;
  27.             for (int i = 0, k = pre; i <= __lg(n); i++)
  28.                 anc[cur][i] = k, k = anc[k][i];
  29.             for (const auto& i : edge[cur])
  30.                 if (i != pre) build(i, cur);
  31.             tout[cur] = t++;
  32.         }; build(0, 0);
  33.         auto isanc = [&](int a, int b) {
  34.             return tin[a] <= tin[b] && tout[a] >= tout[b];
  35.         };
  36.         auto lca = [&](int a, int b) {
  37.             if (isanc(a, b)) return a;
  38.             if (isanc(b, a)) return b;
  39.             for (int i = __lg(n); i >= 0; i--)
  40.                 if (!isanc(anc[a][i], b)) a = anc[a][i];
  41.             return anc[a][0];
  42.         };
  43.         V<int> w(n, 0), res(n, 0);
  44.         while (m--) {
  45.             static int a, b, k, l; cin >> a >> b >> k, l = lca(a, b);
  46.             w[a] += k, w[b] += k, w[l] -= 2 * k, res[l] += k;
  47.         }
  48.         F<int(int, int)> dfs = [&](int cur, int pre) {
  49.             swap(w[cur], res[cur]);
  50.             for (const auto& i : edge[cur])
  51.                 if (i != pre) res[cur] += dfs(i, cur);
  52.             return res[cur];
  53.         }; dfs(0, 0);
  54.         for (int i = 0; i != n; i++)
  55.             cout << res[i] + w[i] << ' ';
  56.         cout << endl;
  57.     }
  58. }
  59.  
  60. main() {
  61.     ios::sync_with_stdio(false);
  62.     init();
  63.     int t = 1;
  64. #ifdef MULTI_TASKCASE
  65.     cin >> t; cin.ignore();
  66. #endif
  67.     while (t--) solve();
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement