题意简述
一棵以 \(1\) 为根的树，儿子间有先后顺序。初始每个结点上有一个警卫，警卫按照深度优先遍历其子树，儿子间的先后顺序体现在这里，回到起始点后开始新一轮的遍历。yzh 想要从 \(S\) 走到 \(1\)，请问她会在路上遇到多少警卫（\(S\) 点的也算）。
题目分析
法 \(1\)
先来讲一讲我考场上的想法。
首先警卫之间互不干扰，所以分别考虑 \(S \sim 1\) 路径上每一个警卫即可。
发现遇到警卫无非两种情况：相向的双向奔赴、同向的同流合污，即警卫向下走遇到人、警卫向上走遇到人。当然还有 \(S\) 点的特殊情况。见下图。
进一步发现，如果和某一个警卫在一条边上擦肩而过，那么之后就不可能再相遇了，因为至少会相差一步。所以题目中说的循环遍历是幌子。
对于 \(1 \sim S\) 路径上的一点 \(u\)，不妨设 \(f[u]\) 表示按顺序遍历完左边所有点并回来的需要时刻。不难发现，由于每条边都贡献了来回的 \(2\) 次，这就是左边边数的两倍。不妨再设 \(g\) 是 \(f\) 在链上的前缀和。
考虑警卫 \(u\)，假设和 yzh 相遇在点 \(w\)，接下来分别讨论两种情况。
双向奔赴
\(u\) 消耗的时间是 \(dpt[w] - dpt[u] + f[u \ldots fa_w]\)，yzh 消耗的时间是 \(dpt[S] - dpt[w]\)。所以有：
\[\begin{aligned} dpt[w] - dpt[u] + f[u \ldots fa_w] &= dpt[S] - dpt[w] \\ dpt[w] - dpt[u] + g[fa_w] - g[fa_u] &= dpt[S] - dpt[w] \\ 2 dpt[w] + g[fa_w] &= dpt[u] + dpt[S] + g[fa_u] \\ \end{aligned} \]不妨把 \(w\) 变为其在链上的孩子。
\[dpt[w] + g[w] = dpt[u] + dpt[S] + g[fa_u] - 2 \]这一个从 \(S\) 向上回溯的时候，用数据结构维护等号左边，查询等号右边并累加答案。
同流合污
这里注意到在 \(w\) 相遇时左边的点不一定全部访问完，可能只是访问了一部分，记这个一部分为 \(p\)。
\[\begin{aligned} dpt[w] - dpt[u] + f[u ... fa_w] + p &= dpt[S] - dpt[w] \\ 2 dpt[w] + g[fa_w] + p &= dpt[S] + g[fa_u] + dpt[u] \end{aligned} \]同样回溯的时候能够维护并计算。
时间复杂度 \(\Theta(n)\)，但是偷懒用 map 多一个 \(\log\)。
法 \(2\)
很容易想到欧拉序，并且欧拉序上两点间长度就是这两个状态之间的时间间隔。
那么先深搜预处理出每个点在欧拉序上的起点和后一个出现位置。
先把 \(1 \sim S\) 路径上的点在欧拉序上起点打个标记。再枚举在那个点的哪个状态相遇。yzh 到达这个点的步数是确定的，那么我们就能够推出警卫的初始位置。如果这个位置有标记，那么答案加一，并清空标记。
注意到有个小优化：预处理的时候访问到 \(S\) 就可以不用继续搜了。
很简单的做法，时间复杂度 \(\Theta(n)\)，常数很小。
代码
法 \(1\)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <iostream>
#include <cstdio>
#define debug(a) cerr << "Line: " << __LINE__ << " " << #a << endl
#define print(a) cerr << #a << "=" << (a) << endl
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define main Main(); signed main() { return ios::sync_with_stdio(0), cin.tie(0), Main(); } signed Main
using namespace std;
#include <vector>
#include <unordered_map>
#include <cstring>
#include <cctype>
#define P(a) while(a isdigit(c=getchar()))
inline void read(int &x){int c;P(!);x=c-48;P()x=x*10+c-48;}
int n, S, ans;
vector<int> edge[500010];
int dpt[500010], f[500010], g[500010];
bool ed;
unordered_map<int, bool> mm, aa;
void dfs(int now, int fa) {
f[now] = 0;
if (now == S) return ed = true, void();
vector<int> ttt;
for (const auto& to: edge[now]) {
dpt[to] = dpt[now] + 1;
g[to] = g[now] + f[now];
dfs(to, now);
if (!ed) f[now] += f[to] + 2, ttt.push_back(f[now]);
else break;
}
if (ed) {
g[now] += f[now];
for (const auto& x: ttt)
aa[2 * dpt[now] + g[fa] + f[fa] + x] = true;
mm[2 * dpt[now] + g[now]] = true;
if (mm.count(dpt[S] - 2 + g[fa] + f[fa] + dpt[now])) ++ans;
else if (aa.count(dpt[S] + dpt[now] + g[fa] + f[fa])) ++ans;
}
}
void solve() {
read(n);
for (int i = 1, k, v; i <= n; ++i)
for (read(k), edge[i].clear(); k--; read(v), edge[i].push_back(v));
read(S), ed = false, mm.clear(), aa.clear(), ans = 1;
g[1] = 0, dfs(1, 0), printf("%d\n", ans);
}
signed main() {
int t; read(t);
while (t--) solve();
return 0;
}
法 \(2\)
最优解，\(890\) ms。
#include <cstdio>
#include <cstring>
using namespace std;
namespace Fast{
constexpr const int MAX = 1 << 26, yzh_i_love_you = 1314520736;
char buf[MAX], *p = buf;
#define getchar() (*p++)
constexpr inline bool isdigit(const char c) { return c >= '0' && c <= '9'; }
inline void read(int &x){
x = 0; char c = 0;
for (;!isdigit(c); c = getchar());
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
}
}
using namespace Fast;
struct Graph{
struct node{
int to, pre;
} edge[500010 << 1];
int eid, head[500010], tail[500010];
inline void add(int u, int v){
edge[++eid] = {v, 0};
(head[u] ? edge[head[u]].pre : tail[u]) = eid;
head[u] = eid;
}
inline node & operator [] (const int x){
return edge[x];
}
} xym;
int n, S, fa[500010], ans;
int st[500010], nxt[500010 << 1], timer;
bool ed, mark[500010 << 1];
void dfs(int now) {
int pre = st[now] = ++timer;
if (now == S) {
ed = true;
} else {
for (register int i = xym.tail[now], to; to = xym[i].to, i; i = xym[i].pre) {
dfs(to);
if (ed) break;
nxt[pre] = ++timer, pre = timer;
}
}
nxt[pre] = -1;
}
void solve() {
read(n), xym.eid = ans = timer = ed = 0;
for (register int i = 1, k, v; i <= n; ++i)
for (read(k), xym.head[i] = xym.tail[i] = 0; k--; read(v), xym.add(i, v), fa[v] = i);
read(S), dfs(1), memset(mark, 0x00, timer + 1);
for (register int i = S; i; i = fa[i]) mark[st[i]] = true;
for (register int step = 0; S; S = fa[S], ++step)
for (register int i = st[S]; ~i; i = nxt[i]) if (i > step) {
ans += mark[i - step];
mark[i - step] = false;
}
printf("%d\n", ans);
}
signed main() {
fread(buf, 1, MAX, stdin);
int t; read(t);
while (t--) solve();
return 0;
}