BZOJ 5457: 城市

题目链接：​​传送门​​​ 题目大意：
一棵树的每个节点上有一群人，给出这群人的数量和民族
问每棵子树内人数最多的民族和人数是多少

线段树合并
dfs从根往下合并就可以
pair是真的方便
人数作first，民族作second
因为要优先输出民族编号最小的
所以民族加负的
维护的时候直接对pair取max就可以

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct N {
  int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
  e[++num].next = head[fr];
  e[num].to = to;
  head[fr] = num;
}
struct SS {
  int l, r, ll, rr;
  pair<int, int> w;
}tree[A << 4];
int n, m, cnt, rt[A], a, b;
pair<int, int> ans[A];
void insert(int &k, int l, int r, int pos, int val) {
  k = ++cnt; tree[k].ll = l, tree[k].rr = r;
  tree[k].w = make_pair(val, -pos);
  if (l == r) return;
  int m = (l + r) >> 1;
  if (pos <= m) insert(tree[k].l, l, m, pos, val);
  else insert(tree[k].r, m + 1, r, pos, val);
}
int merge(int x, int y) {
  if (!x or !y) return x + y;
  if (tree[x].w.second != tree[y].w.second) tree[x].w = max(tree[x].w, tree[y].w);
  else tree[x].w = make_pair(tree[x].w.first + tree[y].w.first, tree[x].w.second);
  if (tree[x].ll == tree[x].rr) return x;
  int m = (tree[x].ll + tree[x].rr) >> 1;
  tree[x].l = merge(tree[x].l, tree[y].l);
  tree[x].r = merge(tree[x].r, tree[y].r);
  tree[x].w = max(tree[tree[x].l].w, tree[tree[x].r].w);
  return x;
}
void dfs(int fr, int faa) {
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == faa) continue;
    dfs(ca, fr);
    rt[fr] = merge(rt[fr], rt[ca]);
  }
  ans[fr] = tree[rt[fr]].w;
}

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 2; i <= n; i++) {
    scanf("%d%d", &a, &b);
    add(a, b); add(b, a);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    insert(rt[i], 1, m, a, b);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; i++) printf("%d %d\n", -ans[i].second, ans[i].first);
}