题解：P10610 异界之门
_MiyazonoKaori_
·
·
题解
一道不错的二分图最大匹配问题，让我以 4.30MB 的成绩断崖式领先获得了内存上的最优解。
题目就不再次叙述了。
思路：
把题目分两步：
- 构造一个与给定序列 c 对应的合法 DFS 序列（即把每个节点放到某个连续区间）；
- 在该 DFS 顺序下还原哪些边需要操作并给出一个合法的操作次序。
一些约定：
记点数为 n，父节点为 f_i(f_1=0)，初始点权为 w_i，目标 DFS 权值序列为 c_1,\dots,c_n，对任意节点 p 令子树大小为 s_p（即 p 的 DFS 区间长度）；
$pos$ 表示节点在 DFS 序列中的位置索引。
### 定义树形 DP：
令 $F_{p,i}\in\{0,1\}$ 表示能否把子树 $p$ 恰好对应到 $c$ 的区间 $[i,i+s_p-1]$。根的可行性就是答案的起点（希望 $F_{1,1}=1$）。
### 解法：
1. 合并子节点的关键：若节点 $p$ 有 $k$ 个孩子且每个孩子子树大小都等于 $s_{son}$，则孩子在 $p$ 的区间内分别占据 $k$ 个固定的子区间：$i+1,i+1+s_{son},i+1+2s_{son},\dots$。把**孩子集合**与**这些子区间编号集合**视为二分图的左右两端：若某孩子 $u$ 能够匹配某个子区间（即 $F_{u,slot}=1$ 并且该子区间的 $c$ 值可由 $u$ 的最终点权得到），就在二分图上连接相应的边。
2. 因此 $F_{p,i}=1$ 当且仅当该二分图存在一个完美匹配（孩子一一对应子区间）。对每个 $p$ 和每个可能的起始 $i$ 枚举并用匈牙利/最大流判断完美匹配，若匹配成立则记录匹配的孩子顺序以供重建。
3. 重建 DFS 序列：从根的 $i=1$ 开始，按记录的孩子顺序把孩子放到对应的子区间，递归得到完整的排列 $p_1,\dots,p_n$（即某个合法的 DFS 序列）。
4. 构造操作方案：对于某个非根节点 $u$（父为 $v$），在确定的 DFS 序列位置上 $c_{pos(u)}$ 与原始 $w_u$ 的关系只可能落在有限的情形（不操作、在父操作前操作、在父操作后操作），据此把必须在父之前/之后执行的约束建成有向依赖图。
还是详细讲一下 DP 吧（可能跟上文有些许重复）。
### DP 转移：
- 若 $p$ 为叶，则
$$F_{p,i}=1\quad(1\le i\le n)$$
- 若 $p$ 有 $k$ 个孩子，且每个孩子子树大小相同记为 $s_{\text{son}}$。若把 $p$ 放在起点 $i$，则第 $j$ 个子区间的全局起点为
$$\text{pos}_j = i+1+j\cdot s_{\text{son}}\quad(j=0,\dots,k-1).$$
- 孩子 $u$ 能匹配该 $slot$ 的必要且必须条件为两者同时成立：
1. 结构上可行： $F_{u,\text{pos}_j}=1$；
2. 值上可行：目标值 $c_{\text{pos}_j}$ 能由孩子 $u$ 的最终点权得到，即
$$c_{\text{pos}_j}\in\{\,w_u,\; w_u+w_p,\; w_u+c_i\,\}.$$
- 把孩子集合与 $slot$ 集合构成二分图，左为孩子索引，右为 slot 索引；若孩子 $u$ 与 slot $j$ 同时满足上述两项，则连边 $u\!-\!j$。则转移为：
$$F_{p,i}=1 \iff \text{该二分图存在完美匹配}.$$
同时记录匹配映射以便重建孩子的遍历顺序。
**重建与操作顺序**（简要写了）
- 从根取 $i=1$ 且 $F_{1,1}=1$，按记录的匹配把每个父的孩子放到对应的 slot（即对应的 $\text{pos}_j$），递归重建整个 DFS 序列 $p_1,\dots,p_n$。
- 对每个非根节点 $u$（父为 $v$），在重建的位置 $\mathrm{pos}(u)$ 上判断
$$c_{\mathrm{pos}(u)}\in\{\,w_u,\; w_u+w_v,\; w_u+c_{\mathrm{pos}(v)}\,\}$$
分别对应“不操作 / 前置操作 / 后置操作”，由此建立先后依赖（若子需在父之前则 $u\to v$，若需在父之后则 $v\to u$），对需要操作的节点做拓扑排序得到合法操作序列。
**时间复杂度分析（貌似是最复杂的）**
- 设对节点 $p$，孩子数为 $k_p$，子树大小为 $s_p$。枚举起点 $i$ 的次数为 $O(n-s_p+1)$；对每个 $i$ 构建的二分图规模为 $k_p\times k_p$，用朴素匈牙利（DFS 增广）最坏代价约 $O(k_p^3)$。因此对节点 $p$ 的代价为
$$O\big((n-s_p+1)\cdot k_p^3\big).$$
- 总体复杂度上界为
$$O\Big(\sum_{p} (n-s_p+1)\,k_p^3\Big).$$
该表达是较松的理论上界，极端最坏情形可达多项式高次（粗略可达 $O(n^4)$），但在实际与题目给定的结构与数据下常能通过。
- 常见优化与更紧复杂度：
- 用 Hopcroft–Karp 或 Dinic 替代朴素匈牙利，单次二分图匹配复杂度可降为 $O(\sqrt{k}\cdot E)=O(k^{2.5})$，则节点代价变为 $O((n-s_p+1)\,k_p^{2.5})$，总体为
$$O\Big(\sum_p (n-s_p+1)\,k_p^{2.5}\Big).$$
- 剪枝：只有当父位点的 $c_i$ 与 $w_p$ 等可能值之一匹配时才尝试枚举该 $i$，以及先用子树可行性 $F_{u,\cdot}$ 过滤边，均能显著减少常数与实际耗时。
但是显然不需要优化。
## CODE:
通过强大的 GPT-5 mini 优化了我的代码，但我并不理解为什么它这么喜欢用 `function`。
```cpp
#include<bits/stdc++.h>
//#include <bits/extc++.h>
#define endl '\n'
#define ll long long
#define close_f fclose(stdin);fclose(stdout);
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define il inline
#define re register
#define PII pair<int,int>
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
il int read();
il void write(int x);
il int gcd(int a,int b);
il int lcm(int a,int b);
il ll Pow(ll a,ll n,ll mod);
il int euler_sieve(int n);
/*
gcd(a,b)
lcm(a,b)
Pow(a,n,1) or Pow(a,n,mod)
euler_sieve(n)
*/
/*--------------------------------*/
int main(){
int n=read();
vector<int> par(n+1);
vector<ll> w(n+1);
for(int i=1;i<=n;i++) cin>>par[i]>>w[i];
vector<ll> c(n+2);
for(int i=1;i<=n;i++) cin>>c[i];
vector<vector<int>> g(n+1);
int root = 1;
for(int i=2;i<=n;i++) g[par[i]].push_back(i);
vector<int> sz(n+1,0);
function<void(int)> dfs_sz = [&](int u){
sz[u]=1;
for(int v: g[u]){ dfs_sz(v); sz[u]+=sz[v]; }
};
dfs_sz(root);
vector<int> order;
function<void(int)> dfs_ord = [&](int u){
for(int v: g[u]) dfs_ord(v);
order.push_back(u);
};
dfs_ord(root);
vector<vector<char>> f(n+1);
vector<unordered_map<int, vector<int>>> choice(n+1);
for(int u: order){
int s = sz[u];
f[u].assign(n+2, 0);
if(g[u].empty()){
for(int i=1;i+ s -1<=n;i++) f[u][i]=1;
continue;
}
int k = (int)g[u].size();
int child_sz = sz[g[u][0]];
for(int i=1;i+ s -1<=n;i++){
vector<vector<int>> adj(k);
bool ok=true;
for(int idx=0;idx<k;idx++){
int slot = i + 1 + idx * child_sz;
if(slot>n){ ok=false; break; }
for(int j=0;j<k;j++){
int v = g[u][j];
if(!f[v][slot]) continue;
ll cv = c[slot];
if(cv==w[v] || cv==w[v]+w[u] || cv==w[v]+c[i]){
adj[j].push_back(idx);
}
}
}
if(!ok) continue;
vector<int> matchR(k, -1), matchL(k, -1);
function<bool(int,vector<char>&)> aug = [&](int x, vector<char>& seen)->bool{
for(int y: adj[x]){
if(seen[y]) continue;
seen[y]=1;
if(matchR[y]==-1 || aug(matchR[y], seen)){
matchR[y]=x; matchL[x]=y; return true;
}
}
return false;
};
int cnt=0;
for(int x=0;x<k;x++){
vector<char> seen(k,0);
if(aug(x, seen)) cnt++;
else break;
}
if(cnt==k){
f[u][i]=1;
vector<int> ord(k);
for(int y=0;y<k;y++) if(matchR[y]!=-1) ord[y]=g[u][matchR[y]]; else ord[y]=0;
choice[u][i]=ord;
}
}
}
vector<int> pos2node(n+1,0);
function<void(int,int)> build = [&](int u,int i){
pos2node[i]=u;
if(g[u].empty()) return;
int k = (int)g[u].size();
int child_sz = sz[g[u][0]];
auto &ord = choice[u][i];
for(int slot=0;slot<k;slot++){
int v = ord[slot];
int child_pos = i + 1 + slot * child_sz;
build(v, child_pos);
}
};
build(root,1);
vector<int> node2pos(n+1,0);
for(int p=1;p<=n;p++) node2pos[pos2node[p]] = p;
vector<int> needOp(n+1,0);
vector<int> type(n+1,0);
for(int pos=2; pos<=n; pos++){
int u = pos2node[pos];
int p = par[u];
ll cu = c[pos];
if(cu==w[u]){ needOp[u]=0; }
else if(cu==w[u]+w[p]){ needOp[u]=1; type[u]=1; }
else if(cu==w[u]+c[node2pos[p]]){ needOp[u]=1; type[u]=2; }
else needOp[u]=0;
}
vector<vector<int>> adjOp(n+1);
vector<int> indeg(n+1,0);
for(int u=2; u<=n; u++){
if(!needOp[u]) continue;
int p = par[u];
if(needOp[p]){
if(type[u]==1){
adjOp[u].push_back(p); indeg[p]++;
} else if(type[u]==2){
adjOp[p].push_back(u); indeg[u]++;
}
}
}
queue<int> q;
for(int i=1;i<=n;i++) if(needOp[i] && indeg[i]==0) q.push(i);
vector<int> ops;
while(!q.empty()){
int u=q.front(); q.pop(); ops.push_back(u);
for(int v: adjOp[u]){ indeg[v]--; if(indeg[v]==0) q.push(v); }
}
cout<<ops.size()<<"\n";
for(size_t i=0;i<ops.size();i++){ if(i) cout<<' '; cout<<ops[i]; } cout<<"\n";
for(int i=1;i<=n;i++){ if(i>1) cout<<' '; cout<<pos2node[i]; } cout<<"\n";
return 0;
}
/*--------------------------------*/
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
inline int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
inline ll Pow(ll a, ll n, ll mod) {
ll ans = 1;
a %= mod;
while (n) {
if (n & 1) {
ans = (ans * a) % mod;
}
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
inline int euler_sieve(int n) {
int cnt = 0;
const int N = n + 5;
int prime[N];
bool vis[N];
memset(vis, 0, sizeof(vis));
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[cnt++] = i;
for (int j = 0; j < cnt; j++) {
if (i * prime[j] > n) {
break;
}
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
return cnt;
}
```