(mathcal{Description})
Link.
给一棵 (n) 个点的树，从某个点出发，遍历时必须走到已经走过的连通块所邻接的编号最小的结点。求从每个点出发，走到 (1) 号结点所需额外走的结点（即走到块的大小 (-1)）。
(nle2 imes10^5)。
(mathcal{Solution})
把 (1) 提为根，那么一个点到根最大的阻碍就是路径上编号最大的结点。记 (mx_u) 表示 (1) 到 (u) 的最大结点编号，并令 (R(u,l)) 表示从 (u) 出发，向其子树，仅经过编号严格小于 (l) 的点能够到达的点的个数（(u) 一定产生贡献，所以至少为 (1)），DP 状态 (f(u)) 表示 (u) 的答案。
现令 (u) 是 (v) 的父亲，考虑 (u) 对 (v) 的转移。
-
若 (mx_v=v)，显然 (u) 不会往 (v) 走，所以要加上 (R(v,mx_u))。
-
否则若 (mx_u=u)，(v) 就会比 (u) 多在子树内卡一会儿。即 (R(v,u)-[v<mx_{fa_u}]R(v,mx_{fa_u}))，后一项是减去重复的贡献。
最后，加上 (u) 到 (1) 的贡献 (f(u))。
可以用暴搜加上记忆化直接计算 (R(u,l))。考虑到搜索时会被子树内一些比 (l) 大的结点所拦截，那么被遍历的连通块就不满足需要计算 (R) 的转移限制。所以遍历到的总点数 (mathcal O(n))。故复杂度 (mathcal O(n))。
(mathcal{Code})
#include <map>
#include <cstdio>
typedef std::pair<int, int> pii;
const int MAXN = 2e5;
int n, ecnt, head[MAXN + 5], fa[MAXN + 5], mx[MAXN + 5], ans[MAXN + 5];
std::map<pii, int> rch;
struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
inline int max_ ( const int a, const int b ) { return a < b ? b : a; }
inline void link ( const int s, const int t ) {
graph[++ ecnt] = { t, head[s] };
head[s] = ecnt;
}
inline void init ( const int u ) {
mx[u] = max_ ( u, mx[fa[u]] );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa[u] ) {
fa[v] = u, init ( v );
}
}
}
inline int reach ( const int u, const int lim ) {
pii sta ( u, lim );
if ( rch.count ( sta ) ) return rch[sta];
int ret = 1;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa[u] && v < lim ) {
ret += reach ( v, lim );
}
}
return rch[sta] = ret;
}
inline void solve ( const int u ) {
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa[u] ) {
if ( mx[v] == v ) ans[v] = reach ( v, mx[u] );
else if ( mx[u] == u ) {
ans[v] = reach ( v, u ) - ( v > mx[fa[u]] ? 0 : reach ( v, mx[fa[u]] ) );
}
ans[v] += ans[u];
solve ( v );
}
}
}
int main () {
scanf ( "%d", &n );
for ( int i = 1, u, v; i < n; ++ i ) {
scanf ( "%d %d", &u, &v );
link ( u, v ), link ( v, u );
}
init ( 1 );
solve ( 1 );
for ( int i = 2; i <= n; ++ i ) printf ( "%d%c", ans[i], i ^ n ? ' ' : '
' );
return 0;
}