BZOJ #5457: 城市 [线段树合并]

线段树合并的板子题，每次从下到上合并就完事了

// by Isaunoya

#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, n) for (int i = j; i <= n; i++)

#define in cin

#define out cout

#define pii pair<int, int>

#define fir first

#define sec second

int n, m;

const int maxn = 4e5 + 54;

int rt[maxn], ls[maxn << 5], rs[maxn << 5], cnt = 0;

pii mx[maxn << 5], ans[maxn];

void upd(int& p, int l, int r, int x, int v) {

  if (!p) p = ++cnt;

  if (l == r) {

    mx[p] = { v, -x };

    return;

  }

  int mid = l + r >> 1;

  if (x <= mid)

    upd(ls[p], l, mid, x, v);

  else

    upd(rs[p], mid + 1, r, x, v);

  mx[p] = max(mx[ls[p]], mx[rs[p]]);

}

int merge(int x, int y, int l, int r) {

  if (!x || !y) return x | y;

  if (l == r) {

    mx[x].fir += mx[y].fir;

    return x;

  }

  int mid = l + r >> 1;

  ls[x] = merge(ls[x], ls[y], l, mid);

  rs[x] = merge(rs[x], rs[y], mid + 1, r);

  mx[x] = max(mx[ls[x]], mx[rs[x]]);

  return x;

}

vector<int> g[maxn];

int fa[maxn];

void dfs(int u) {

  //  for (int v : g[u])

  //    if (fa[u] ^ v) fa[v] = u, dfs(v);

  for (int i = 0; i < g[u].size(); i++) {

    int v = g[u][i];

    if (fa[u] ^ v) {

      fa[v] = u;

      dfs(v);

    }

  }

  ans[u] = mx[rt[u]];

  rt[fa[u]] = merge(rt[fa[u]], rt[u], 1, n);

}

signed main() {

  // code begin.

  ios ::sync_with_stdio(false);

  cin.tie(0), cout.tie(0);

  in >> n >> m;

  rep(i, 2, n) {

    int u, v;

    in >> u >> v;

    g[u].push_back(v);

    g[v].push_back(u);

  }

  rep(i, 1, n) {

    int a, b;

    in >> a >> b;

    upd(rt[i], 1, n, a, b);

  }

  dfs(1);

  rep(i, 1, n) out << -ans[i].sec << ' ' << ans[i].fir << '\n';

  return out.flush(), 0;

  // code end.

}