题目描述
include [HTML_REMOVED]
using namespace std;
int n, m;
int w[3000], p[3000];
long long sumw[3000];
vector[HTML_REMOVED]> son(3000);
int flag[3000];
set[HTML_REMOVED] seg;
long long dfs(int root)
{
seg.insert(root);
long long son_w = 0;
for (auto x : son[root])
{
if (flag[x] == 0)
continue;
son_w += dfs(x);
}
sumw[root] = w[root] + son_w;
return sumw[root];
}
int query(int root)
{
long long wsigma = LONG_LONG_MAX;
int pos = 9;
for (auto x : seg)
{
long long t = abs(sumw[root] - 2 * sumw[x]);
// cout << t << ” “;
if (t < wsigma)
{
wsigma = t;
pos = x;
}
}
return pos;
}
bool judege(int root, int rq)
{
if (root == rq)
return true;
int flags = 0;
for (auto x : son[root])
{
flags |= judege(x, rq);
if (flags)
{
return flags;
}
}
return flags;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i)
cin >> w[i];
for (int i = 2; i <= n; i)
{
cin >> p[i];
son[p[i]].insert(i);
}
int rq;
int root = 1;
while (m–)
{
memset(flag, 1, sizeof(flag));
cin >> rq;
root = 1;
while (1)
{
seg.clear();
dfs(root);
if (seg.size() == 1)
break;
int pos = query(root);
cout << pos << ” “;
if (judege(pos, rq))
root = pos;
else
flag[pos] = 0;
}
cout << endl;
}
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla