首先,有一个显然的贪心,假设我们最开始在点 \(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
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性