翻车笔记_ [ZJOI2012]灾难 [倍增, LCA, 清奇脑回路]

要善于把握算法的本质, 和使用的情景

懵逼的 题目

qwq

扯淡的 题解

当时的想法是….在dfs的时候…我找到一个点…就把他所有入度的LCA之上的点的答案都加一…然后想到树剖…结果rqy把这个想法hack了23333
因为在dfs(或者说拓扑排序)的时候你的树还没有建好…谈不上树剖…网上有说什么动态树剖的感觉非常神
那我们考虑找一个能在不断在下方添加节点的情况下还能求LCA的算法…就是倍增了…

还有一个挺巧妙的地方就是把这个节点挂在他所有入度的LCA下面, 这样就可以更快的统计答案了(据说这玩意叫支配树?)…

沙茶的 代码

又忘了在倍增LCA的时候判断是不是deep[x] == deep[y]x == y了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**************************************************************
Problem: 2815
User: Cansult
Language: C++
Result: Accepted
Time:404 ms
Memory:31560 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXL (20 + 5)
const int root = 0;
using namespace std;
struct edg
{
int from, to, next;
}b[MAXM << 1], bn[MAXN << 1];
int g[MAXN], cntb, n, gn[MAXN], cntn, size[MAXN], du[MAXN], d[MAXN][MAXL], lgn, ans[MAXN], deep[MAXN];
vector<int> fa[MAXN];
int lg(int x)
{
int re = 0;
for (; (1 << re) <= x; ++re)
continue;
return re;
}
void adn(edg* bx, int* gx, int& cntx, int from, int to)
{
bx[++cntx].next = gx[from];
bx[cntx].from = from, bx[cntx].to = to;
gx[from] = cntx;
}
int lca(int x, int y)
{
if (deep[x] < deep[y])
swap(x, y);
for (int i = lgn; i >= 0; i--)
if (deep[d[x][i]] >= deep[y])
x = d[x][i];
if (x == y)
return x;
for (int i = lgn; i >= 0; i--)
if (d[x][i] != d[y][i])
x = d[x][i], y = d[y][i];
return d[x][0];
}
void init()
{
queue<int> q;
fa[root].push_back(root);
deep[root] = 1;
d[root][0] = 1;
q.push(root);
while (!q.empty())
{
int dq = q.front();
q.pop();
int dqfa = fa[dq][0];
for (int i = 1; i < fa[dq].size(); i++)
dqfa = lca(dqfa, fa[dq][i]);
d[dq][0] = dqfa;
deep[dq] = deep[dqfa] + 1;
adn(bn, gn, cntn, dqfa, dq);
adn(bn, gn, cntn, dq, dqfa);
for (int i = 1; i <= lgn; i++)
d[dq][i] = d[d[dq][i - 1]][i - 1];
for (int i = g[dq]; i; i = b[i].next)
{
fa[b[i].to].push_back(dq);
du[b[i].to]--;
if (!du[b[i].to])
q.push(b[i].to);
}
}
}
void dfs(int dq, int fa)
{
ans[dq] = 1;
for (int i = gn[dq]; i; i = bn[i].next)
if (bn[i].to != fa)
{
dfs(bn[i].to, dq);
ans[dq] += ans[bn[i].to];
}
}
int main()
{
scanf("%d", &n);
lgn = lg(n);
for (int i = 1; i <= n; i++)
for (int srx; ; )
{
scanf("%d", &srx);
if (!srx)
break;
adn(b, g, cntb, srx, i);
++du[i];
}
for (int i = 1; i <= n; i++)
if (!du[i])
{
++du[i];
adn(b, g, cntb, root, i);
}
init();
dfs(root, root);
for (int i = 1; i <= n; i++)
printf("%d\n", ans[i] - 1);
return 0;
}

By zz Cansult