P7353 解题报告
flyingfrog
·
·
题解
前言
模拟赛挂分挂完，直接来补 T4，花半天一路学了点双、圆方树（菜还有理了），但是 @Hoks 的思路对我来说不太直接，所以决定自己重新写一篇。
思路
赛时看到，最先想到割点，打算写个显然假的做法：Tom 在割点就是 Yes，否则就是 No。
但是割点挂了。 正解的确与割点有关。
初始在割点：
一种显然的策略：
- Tom 初始在割点。
- Tom 每一步走到另一个能使 Jerry 能活动的点双变少的割点。
- Tom 最后一步抓住 Jerry。
一些深入思考：
- 每个割点连接多个不同点双，策略的可行性取决于 Jerry 所在联通块能不能被 Tom 缩小。
- Tom 如果不能每一步都到达一个割点，Jerry 就可以逃跑，这个策略就会寄。
总结关键词：割点，到达，位置——圆方树。
一直到这一步应该都是好理解的。那么在原图上建出圆方树。以 Tom 的位置为树根，向 Jerry 所在子树越过方点移动。每次到达的圆点和上一个圆点必须有边连接，不然 Jerry 就会逃跑。
钦定点 1 作为树根，f_u，g_u 分别表示点 u 内外子树的可行行，考虑 dp：
内子树 f（第一遍 dfs）
对于每个圆点 u 之于其子树的可行性 f_{u} 如果为 1，那么它的儿子方点的儿子圆点（以下称为孙子圆点 sv）对于 u 必须都在原图上可达即 p(u, sv) = 1（不然 Jerry 跑到这个子树就寄），而且必须有 f_{sv} = 1 。就是说：
\forall sv, f_{sv} \land p(u, sv), f_u = 1
然而这样 dp 是存在缺陷的。考虑下图：
建出圆方树：
简单模拟一下可以得到 f=\{0, 1, 1, 1, 1\}。然而对于询问 1, 2，2 在 1 的子树中，如果直接从 f_1 就会得到答案为 No，不符合实际。究其原因在于 Jerry 只能在编号 7 的点双里移动而到不了 6 去，但 f_1 却是包括了 7 和 6 的答案。
解决方法也很简单，把 f 记录的对象从圆点扩大到方点。
对于每个方点 u 之于其子树的可行性 f_{u} 如果为 1，那么它的儿子圆点 v 对于父亲圆点 fa_u 必须都在原图上可达即 p(fa_u, v) = 1，而且必须有 f_{v} = 1 。就是说：
\forall v, f_{v} \land p(fa_u, v), f_u = 1
用这种 dp 得到的 f=\{0, 1, 1, 1, 1, 0, 1\}，对于询问 1, 2，查询 2 所在 1 的子树的根（一定是 1 的一个儿子方点）也就是 7，得到 Yes，符合实际。
不过为了下面对 g 的递推方便一些，在这里修改一下 f 的定义：f_u 表示 u 的儿子或孙子圆点符合条件的数量，同时定义辅助数组 son 记录圆点的孙子数和方点的儿子数，dp：
f_u = \sum_{v \in sons_u}[p(u, v) \land(f_v = son_v)]
判断改成 f_u = son_u 即可。
外子树 g（第二遍 dfs）
1. 祖父圆点 $ga$ 的外子树。要求 $ga$ 能到达 $u$ 且 $g_{ga} = 1$。
2. $u$ 的兄弟圆点 $br$。要求 $br$ 能到达 $u$ 且 $f_{br} = son_{br}$。
3. 父亲方点的兄弟方点 $uc$。这些方点不与 $u$ 直接连接，所以不用判断是否能到达。要求 $f_{uc} = son_{uc}$。
第一点，直接设定 $g_u$ 的初值为 $g_{ga} \land p(ga, u)$。
第二点，遍历并判断。
对于第三点中的 $uc$，不用遍历，因为 $\sum f_{uc}=f_{ga}-f_{fa}$，$\sum son_{uc}=son_{ga}-son_{fa}$，所以直接判断 $f_{ga} - f_{fa} = son_{ga} - son_{fa}$ 就行。
不用记录方点，因为外子树只有一个。
### 初始不在割点
到目前为止都是对初始在割点情况的说明。而对与 Tom 初始不在割点的情况，可以遍历一遍所有圆点看是否有点 $u$ 满足 $f_u = son_u$ 且 $g_u = 1$。
如果有，那不管在不在割点，所有询问都输出 Yes 就可以。因为只要 Tom 到这个点，不管 Jerry 在内子树还是外子树，都可以采用上面的策略。
而如果没有，不管 Tom 移动到哪个点，Jerry 只要移动到 Tom 抓不到的部分去就可以赢得比赛，所以初始不在割点就是 No。
不用特意判断是否在割点。不是割点的点 $f$ 和 $g$ 一定不满足条件。
## 代码实现
处理询问时会遇到一个问题，就是如何判断 $y$ 是否在 $x$ 的子树内。可以利用树剖的思想，一个子树内的 $dfn$ 一定是连续的，所以在 dfs 处理 $f$，$g$ 的时候顺手处理出 $in$ 和 $out$ 数组，$in$ 数组记录遍历到该点时的 $tim$，$out$ 数组记录离开该点时的 $tim$，那么只要满足 $in_x \le in_y \le out_x$ 就可以判定 $y$ 在 $x$ 的子树内。
而当 $b$ 在 $a$ 子树内时也可以利用这一点，遍历 $a$ 的所有儿子方点 $v$，若 $in_v \le in_b \le out_v$，那么 $v$ 就是可以得出答案的方点。
```cpp
#include <bits/stdc++.h>
using namespace std;
const string name = "P7353";
const int N = 2e5 + 2;
int n, m, q, tim, top, cnt;
int dfn[N], low[N], stk[N], fa[N], son[N], in[N], out[N];
int dp[N][2];
set <int> g[N];
vector <int> tr[N];
void tarjan(int u, int fa){
dfn[u] = low[u] = ++ tim;
stk[++ top] = u;
for(int v : g[u]){
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[v], low[u]);
if(low[v] >= dfn[u]){
int r = ++ cnt;
tr[r].push_back(u);
tr[u].push_back(r);
while(stk[top + 1] != v){
int t = stk[top];
tr[r].push_back(t);
tr[t].push_back(r);
top --;
}
}
}else if(v != fa)
low[u] = min(dfn[v], low[u]);
}
}
void dfs1(int u, int f){
in[u] = ++ tim;
for(int v : tr[u]){
if(v == f) continue;
fa[v] = u;
in[v] = ++ tim;
for(int vv : tr[v]){
if(vv == u) continue;
fa[vv] = v, son[u] ++, son[v] ++;
dfs1(vv, v);
if(g[u].count(vv) && dp[vv][0] == son[vv])
dp[u][0] ++, dp[v][0] ++;
}
out[v] = tim;
}
out[u] = tim;
}
void dfs2(int u, int f){
if(!f) dp[u][1] = 1;
else dp[u][1] = (g[u].count(f) & dp[f][1] & (dp[f][0] - dp[fa[u]][0] == son[f] - son[fa[u]]));
for(int v : tr[fa[u]]){
if(v == u || v == f) continue;
dp[u][1] &= (g[u].count(v) & (dp[v][0] == son[v]));
}
for(int v : tr[u]){
if(v == fa[u]) continue;
for(int vv : tr[v]){
if(vv == fa[v]) continue;
dfs2(vv, u);
}
}
}
bool check(int u, int v){
for(int t : tr[u]){
if(t == fa[u]) continue;
if(in[t] <= in[v] && in[v] <= out[t]){
return dp[t][0] == son[t];
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q; cnt = n;
for(int i = 1; i <= m; i ++){
int u, v; cin >> u >> v;
g[u].insert(v);
g[v].insert(u);
}
tarjan(1, 0); tim = 0;
dfs1(1, 0);
dfs2(1, 0);
for(int i = 1; i <= n; i ++){
if(dp[i][0] == son[i] && dp[i][1]){
while(q --) cout << "Yes\n";
return 0;
}
}
while(q --){
int u, v; cin >> u >> v;
if(in[u] <= in[v] && in[v] <= out[u]){
if(check(u, v)) cout << "Yes\n";
else cout << "No\n";
}else{
if(dp[u][1]) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}
```