Up and Down the Tree
题目链接：https://www.luogu.org/problem/CF1065F
数据范围：略。
题解：
我们把每个叶子向它上面$k$个点连边，然后trajan缩点。
表示如果一个$SCC$中的叶子能走到，剩下的就都能。
然后我们就求一个最长的根缀链即可。
代码：
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define N 1000010
using namespace std;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
struct Graph {
int head[N], to[N << 1], nxt[N << 1], tot;
inline void add(int x, int y) {
to[ ++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
}G1, G2;
int f[21][N];
int dep[N], low[N], cnt, sz[N], F[N], st[N], top, blg[N];
bool vis[N], ins[N];
queue <int> q;
void tarjan(int p) {
dep[p] = low[p] = ++cnt;
vis[p] = ins[p] = true;
st[ ++ top] = p;
for (int i = G1.head[p]; i; i = G1.nxt[i]) {
if (!vis[G1.to[i]]) {
tarjan(G1.to[i]), low[p] = min(low[p], low[G1.to[i]]);
}
else if (ins[G1.to[i]]) {
low[p] = min(low[p], dep[G1.to[i]]);
}
}
if (dep[p] == low[p]) {
blg[0] ++ ;
int t;
do {
t = st[top -- ];
blg[t] = blg[0];
ins[t] = false;
} while(t != p);
}
}
bool lf[N];
void dfs(int p, int fa) {
f[0][p] = fa;
for (int i = 1; i <= 20; i ++ ) {
f[i][p] = f[i - 1][f[i - 1][p]];
}
for (int i = G1.head[p]; i; i = G1.nxt[i]) {
dfs(G1.to[i], p);
}
}
int d[N];
int main() {
// setIO("c");
memset(lf, true, sizeof lf);
int n = rd(), k = rd();
for (int i = 2; i <= n; i ++ ) {
int x = rd();
G1.add(x, i);
lf[x] = false;
}
dfs(1, 1);
for (int i = 2; i <= n; i ++ ) {
if (lf[i]) {
int x = i;
for (int j = 20; ~j; j -- ) {
if (k & (1 << j)) {
x = f[j][x];
}
}
G1.add(i, x);
}
}
tarjan(1);
for (int i = 1; i <= n; i ++ ) {
for (int j = G1.head[i]; j; j = G1.nxt[j]) {
if (blg[i] != blg[G1.to[j]]) {
G2.add(blg[i], blg[G1.to[j]]);
d[blg[G1.to[j]]] ++ ;
}
}
}
for (int i = 2; i <= n; i ++ ) {
if (lf[i]) {
sz[blg[i]] ++ ;
}
}
for (int i = 1; i <= blg[0]; i ++ ) {
F[i] = sz[i];
}
q.push(blg[1]);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = G2.head[x]; i; i = G2.nxt[i]) {
F[G2.to[i]] = max(F[x] + sz[G2.to[i]], F[G2.to[i]]);
d[G2.to[i]] -- ;
if (!d[G2.to[i]]) {
q.push(G2.to[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= blg[0]; i ++ ) {
ans = max(ans, F[i]);
}
cout << ans << endl ;
// fclose(stdin), fclose(stdout);
return 0;
}