题目大意
给你一个树,每个节点上有有一个部落,以及部落的人数,要你求出每个节点的子树里面人数最多的部落是哪一个(人数相同部落编号最小的)。
思路
考虑树的dfs序,然后分治处理,每层只处理跨过mid的区间,然后就完了。
时间复杂度\(O(nlogn)\),但常数比树上启发式合并小。
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define Re register
#define ll long long
bool st;
const int N = 400000 + 5;
inline int read() {
int ret = 0, f = 0; char ch;
do {
ch = getchar();
if (ch == '-') f = 1;
} while (ch < '0' || ch > '9');
do {
ret = (ret << 3) + (ret << 1) + ch - '0';
ch = getchar();
} while (ch <= '9' && ch >= '0');
return f ? - ret : ret;
}
inline void hand_in() {
freopen("endless.in", "r", stdin);
freopen("endless.out", "w", stdout);
}
struct Graph {
int to[N << 1], nxt[N << 1], head[N], cnt;
inline void add(int x, int y) {
++cnt;
to[cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
}
}G;
int n, m, a[N], b[N];
struct Node { int val, id; }ans[N];
int dfn[N], sz[N], tot, id[N];
inline void dfs(int u, int fa) {
dfn[u] = ++ tot;
id[tot] = u;
sz[u] = 1;
for (Re int i = G.head[u];i;i = G.nxt[i]) {
int v = G.to[i];
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int c[N], sta[N], top;
inline void cal(int l, int r) {
if (l >= r) {
if (sz[id[l]] == 1) ans[id[l]].id = a[id[l]], ans[id[l]].val = b[id[l]];
return;
}
int mid = (l + r) >> 1;
cal(l, mid), cal(mid + 1, r);
top = 0;
int mx = 0, ids, p = mid + 1;
for (int i = mid;i >= l; --i) {
int u = id[i];
sta[++top] = a[u];
c[a[u]] += b[u];
if (c[a[u]] > mx || (c[a[u]] == mx && ids > a[u])) mx = c[a[u]], ids = a[u];
int ed = i + sz[u] - 1;
if (ed <= mid || ed > r) continue;
while (p <= ed) {
int v = id[p];
c[a[v]] += b[v];
sta[++top] = a[v];
if (c[a[v]] > mx || (c[a[v]] == mx && ids > a[v])) mx = c[a[v]], ids = a[v];
p ++;
}
ans[u].val = mx, ans[u].id = ids;
}
for (Re int i = 1;i <= top; ++i) c[sta[i]] = 0;
}
bool ed;
int main() {
hand_in();
n = read(), m = read();
for (Re int i = 1, u, v;i < n; ++i) {
u = read(), v = read();
G.add(u, v), G.add(v, u);
}
for (Re int i = 1;i <= n; ++i) {
a[i] = read(), b[i] = read();
}
dfs(1, 0), cal(1, n);
for (int i = 1;i <= n; ++i) {
printf("%d %d\n", ans[i].id, ans[i].val);
}
return 0;
}