题目描述
模拟决策树
样例
in
5 2
10 50 10 10 20
1 1 3 3
5
3
out
2 5
2 5 3 4
算法1
(正解 咋网上的全是错的题解) $O(n^2+nm)$
首先建立可达矩阵(二维数组用于判断$i\to j$有无联通路径),建搜索树,然后每个询问模拟一遍搜索。
建树过程如下:
- 首先选取最大的$w$点记为$root$,代表搜索树的根节点
- 将当前节点(记作$p$)的子节点从当前图全部删去
- 计算图的剩余部分的最大的$w$点(记作$q_1$),记录$tr[p][false]=q_1$(即在决策树搜索过程中,如果当前搜索节点不是$p$节点的子节点,那么接下来搜索$q_1$节点)
- 递归搜索$q_1$节点
- 将剩余点全部删去,恢复步骤
2
删去的点 - 计算图的剩余部分的最大的$w$点(记作$q_2$),记录$tr[p][true]=q_2$(即在决策树搜索过程中,如果当前搜索节点是$p$节点的子节点,那么接下来搜索$q_2$节点)
- 递归搜索$q_2$节点
- 恢复步骤
5
删去的点
其中$2-8$是一个递归过程, 退出的条件为剩余的节点数目$<1$(可以使用$-1$标记), 单次执行(不考虑递归)该函数复杂度为$O(n)$,每个节点最多一次出现在$p$位置(因为显然,询问两次同一个节点是没有意义的),所以该函数最多被执行$n$次。
然后是每次搜索过程:
从$root$节点开始,根据上文提到的$false,true$规则进行迭代搜索,直到当前节点为$-1$
举例来说:
样例的搜索树结构如下
节点 | false | true |
---|---|---|
$2(root)$ | $5$ | $-1$ |
$5$ | $3$ | $-1$ |
$3$ | $-1$ | $4$ |
$4$ | $-1$ | $-1$ |
样例的搜索过程如下
$5:2(false)\to 5(true)\to -1$
$3:2(false)\to 5(false)\to 3(true)\to 4(false)\to -1$
时间复杂度
计算可达矩阵:$O(n^2)$
递归生成搜索树:$n\times O(n)$
计算单次结果:$O(n)$
总复杂度$n\times n+n\times m+n^2=O(n^2+nm)$
C++ 代码
#include<iostream>
#include<vector>
#include<stack>
#include<cassert>
const int maxn = 2e3 + 10;
using ll = long long;
std::vector<int> e[maxn];
int x[maxn][2], fz[maxn][maxn];
ll pri[maxn], now[maxn];
int prt[maxn], block[maxn], bl[maxn];
int n, m;
ll sum;
int c, sz;
void dfs0(int i) {//更新每个结点的权值
if (block[i]) {
for (int j: e[i])dfs0(j);
return;
}
sum += pri[i], now[i] = pri[i];
for (int j: e[i]) {
dfs0(j);
if (!block[j])now[i] += now[j];
}
sz++;
}
int refresh() {//计算当前最大w值的节点
sz = 0, c = 0, sum = 0;
dfs0(1);
for (int i = 1; i <= n; i++) {
if (!block[i] && std::abs(sum - 2 * now[i]) < std::abs(sum - 2 * now[c]))c = i;
}
return c;
}
void dfs1(int p) {//递归函数
if (sz == 1)return;
bl[p] = 1;
std::vector<int> dd, dd2;
for (int i = 1; i <= n; i++)if (fz[p][i] && !block[i])block[i] = 1, dd.push_back(i);
//步骤2
int l = refresh();//步骤3
if (bl[l])l = 0;
if (l)dfs1(l);//步骤4
x[p][0] = l;
for (int i = 1; i <= n; i++) if (!block[i]) block[i] = 1, dd2.push_back(i);
for (auto i: dd)block[i] = 0; //步骤5
int r = refresh(); //步骤6
if (bl[r])r = 0;
if (r)dfs1(r); //步骤7
x[p][1] = r;
for (auto i: dd2)block[i] = 0; //步骤8
bl[p] = 0;
}
void dfs2(int i) {//递归函数,用于计算可达矩阵
fz[i][i] = 1;
for (int j: e[i]) {
dfs2(j);
for (int k = 1; k <= n; k++)fz[i][k] |= fz[j][k];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%lld", pri + i);
for (int i = 2; i <= n; i++) {//建图
scanf("%d", prt + i);
e[prt[i]].push_back(i);
}
int rt = refresh();// 步骤1
dfs2(1), dfs1(rt);
while (m--) {
int q, s = rt;
scanf("%d", &q);// 递归搜索
while (s) {
printf("%d ", s);
s = x[s][fz[s][q]];
}
putchar('\n');
}
return 0;
}
tql
给大佬跪了