CF1654G Snowy Mountain

首先，有一个显然的贪心，假设我们最开始在点 \(x\) 就是我们会到达一个能到达的最远的可以反复横跳的两个相邻节点（下称平台）称先到达的那个点为 \(y\)，一直跳到没有势能，再继续往下走，那么最终的答案就是 \(2h_x-h_y\)。
这个东西似乎不好优化，那么观察下是否暴力有什么优美的性质。（一般一个做法不好优化的时候可以考虑根号分治/复杂度分析）
形成一个平台至少需要两个高度相同的点 \(a,b\) 不难发现形成一对 \(a,b\) 一定至少需要 \(2h_a\) 个点。感性理解一下（就是说如果要继续利用这个 \(a\) 现有的高度，那么我们不得不另开一个至少大小为 \(a\) 的子树），平台高度至多有 \(\sqrt{2n}\) 种。
证明的话这篇题解有很好的证明

然后 \(bfs\) 精细化实现一下即可（详见代码）。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e5 + 10;
int head[N], cnt = 1, n, h[N], dis[N], vis[N], ans[N];
vector<int> g[N];

struct edge {
	int v, nxt;
} e[N << 2];

inline void aedge(int u, int v) {
	e[++cnt] = {v, head[u]};
	head[u] = cnt;
}

inline void solve(int d) {
	// cerr << d << "\n";
	memset(dis, 0x3f, sizeof dis);
	deque<int> q;
	
	for (auto u: g[d]) {
		q.push_back(u);
		dis[u] = d + 1;
	}
	while (!q.empty()) {
		int u = q.front(); q.pop_front();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if ((h[u] == h[v] || (h[u] < h[v] && dis[u] == h[u])) && dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1, q.push_back(v);
			}
			if (h[u] < h[v] && dis[u] > h[u] && dis[v] > dis[u])
				dis[v] = dis[u], q.push_front(v);
		}
	}

	U(u, 1, n) if (dis[u] == h[u]) chkmin(ans[u], d);
}

int main(){
	//FO("");
	read(n);
	queue<int> q;
	memset(h, 0x3f, sizeof h);
	U(i, 1, n) {
		int x;
		read(x);
		if (x == 1) {
			h[i] = 0;
			q.push(i);
		}
	}
	U(i, 2, n) {
		int u, v;
		read(u, v);
		aedge(u, v);
		aedge(v, u);
	}

	while (!q.empty()) {
		int u = q.front(); q.pop();
		int cur = h[u] + 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (cur < h[v]) {
				h[v] = cur;
				q.push(v);
			}
		}
	}

	U(i, 1, n) {
		ans[i] = h[i];
		bool ok = 0;
		for (int j = head[i]; j; j = e[j].nxt) {
			int v = e[j].v;
			if(h[i] == h[v]) {
				ok = 1;
				break ;
			}
		}
		if(ok) g[h[i]].push_back(i);
	}

	U(i, 0, n) {
		if (g[i].empty()) continue ;
		else solve(i);
	}
	U(i, 1, n) 
		writesp(2 * h[i] - ans[i]);

	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16837375.html