洛谷p2018 树DP
首先，本做法和其他的O(N^2logn)做法是完全不一样的，那种做法比较好理解，我说一下我的做法，感jio是O(Nlogn)，不太会算
首先思考如何获得每一点要如何知道由当前点出发的答案是什么？对于绝大部分点，都有父亲节点和儿子节点，那么对于每一个点都是这么抉择走的。
这里先不看now点，看节点1，如果第一个人从节点1开始要怎么走呢？就是花4次时间， 分别走4跳荧光笔的路径对吧，然后就没节点1什么事情了，接下来的路要靠其他点他们自己去走。
我们假设f[i]为从i点开始往下走完所有节点的最短时间，
g[i]为从i点开始往上走完所有节点的最短时间
那么对于上图而言，要获得节点1的答案就需要获取f数组和g数组。
现在我们考虑如何得出这两个东西。
先思考f[i]怎么获得，f[i]是往下走的所有节点的最短时间，那么对于每一个i节点，我们可以对他所有的儿子f[z]去进行排序！！然后从f[z]比较大的这个儿子节点先走，在走其他的，从大到小走，为什么要这么走呢？这是用了个贪心的做法！！！从一个点要走的步数多，那么你先走他就可以比较快的完成嘛！，所以排个序后贪心的拿就好了，第一个拿的就加0，第二个拿的就加1（因为要多花额外的时间才能走这条路线是不是），。。。。。。最后取一个max，一个点的完成的时间取决于最慢的那个时间。
f[i] = max(f[son] + v)
下一步是考虑g[i],思考一下g[i]怎么来的还是这个图
现在我们看now点，要算g[now]就是要算now点往上要多久才能覆盖全部，所以类比f数组的排序操作，我们需要对
1 - 2，1 - 3， 1 - 4这些边进行排序，然后计算附加权值取max，这些都和f一样，只是不同的是1-now这条边的必定要先走，因为一个点只有一个父亲嘛，你往上走就只会走这条路，然后走到now点的父亲节点就出现了分支，你就需要对这些分支去进行进行排序操作取max就可以得到g啦。
在这个图里面，就是比较g[2], f[3],f[4]的大小，这些你看是不是我们在之前都算出来了呢。
最后答案什么算?很遗憾我们不能简单粗暴的用这个
value[i] = max(max(f[i], g[i]), min(f[i], g[i]) + 1);
ans = min(ans, value[i]);
这样就是对于先走下面全部走完在走上面或者先走上面在走下面，这样子会wa一个点（就是他数据水才AC这么多），你可能是先在下面走一两条边， 在走上面，在继续走下面， 所以还需要对于该点连着的所有边进行一次排序操作就可以了。
对于上面那个图，要算节点1，就是对g[2],f[3],f[now],f[4]去排序算权值就好了。
这样总来说是就是跑两遍dfs就可以出答案拉。感觉就是nlogn，如果不是请教我算~最后代码方面不开O2是跑了48ms，开了o2是跑了33ms
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ll long long
//#define double long double
using namespace std;
#define PI 3.1415926535898
#define eqs 1e-6
const long long max_ = 5000 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
bool cmp(int a, int b) {
return a > b;
}
int temp[max_], tn = 0, n, f[max_], g[max_], father[max_], value[max_];
vector<int> xian[max_];
void dfs(int now, int fa) {
father[now] = fa;
//算i往下需要多少才可以传递完所有人
for (int i = 0; i < xian[now].size(); i++) {
int to = xian[now][i];
if (to == fa)continue;
dfs(to, now);
}
tn = 0;
for (int i = 0; i < xian[now].size(); i++) {
int to = xian[now][i];
if (to == fa)continue;
temp[++tn] = f[to];
}
sort(temp + 1, temp + 1 + tn, cmp);
int v = 0;
for (int i = 1, j = 1; i <= tn; j++, i++) {
v = max(v, temp[i] + j);
}
f[now] = v;
}
void dfs2(int now, int fa) {
tn = 0;
//首先花费1的价值到达父亲节点，然后判断从父亲节点往哪里走
if (father[fa])
temp[++tn] = g[fa];
for (int i = 0; i < xian[fa].size(); i++) {
int to = xian[fa][i];
if (to == father[fa] || to == now)continue;
temp[++tn] = f[to] + 1;
}
sort(temp + 1, temp + 1 + tn, cmp);
int v = 0;
for (int i = 1, j = 0; i <= tn; j++, i++) {
v = max(v, temp[i] + j);
}
g[now] = v; if (now != 1)g[now]++;
for (int i = 0; i < xian[now].size(); i++) {
int to = xian[now][i];
if (to == fa)continue;
dfs2(to, now);
}
}
int main() {
n = read();
for (int i = 2; i <= n; i++) {
int a = read();
xian[a].push_back(i);
xian[i].push_back(a);
}
dfs(1, 0);
dfs2(1, 0);
int ans = f[1];
value[1] = f[1];
for (int i = 2; i <= n; i++) {
/* value[i] = max(max(f[i], g[i]), min(f[i], g[i]) + 1); ans = min(ans, value[i]);*/
tn = 0;
temp[++tn] = g[i] - 1;
for (int j = 0; j < xian[i].size(); j++) {
int to = xian[i][j];
if (to == father[i])continue;
temp[++tn] = f[to];
}
sort(temp + 1, temp + 1 + tn, cmp);
int v = 0;
for (int x = 1, j = 1; x <= tn; j++, x++) {
v = max(v, temp[x] + j);
}
value[i] = v;
ans = min(ans, value[i]);
}
cout << ans + 1 << endl;
for (int i = 1; i <= n; i++) {
if (value[i] == ans) {
cout << i << " ";
}
}
return 0;
}
查看6道真题和解析
投递深圳同为数码等公司10个岗位