对于每个m其实都建了当前状态对应的树,根据当前的树的总权值可以计算出龙龙的工作量就是总权值的两倍减去最远节点的权值。
C++参考代码一手代码,有待优化,仅供参考。
#include
using namespace std;
const int N = 1e5 + 10;
int fa[N], v[N], wei[N];
int farpos, Tree_wei;
int find_wei(int w)
{
if (wei[w] == 0 && !v[w]) wei[w] = find_wei(fa[w]) + 1;
return wei[w];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &fa[i]);
if (fa[i] == -1)
{
v[i] = 1;
farpos = i;
}
}
//压缩路径求距离 复杂度相当于总权值
for (int i = 1; i <= n; i++)
{
if (v[i] || wei[i]) continue;
else wei[i] = find_wei(i);
}
for (int i = 1; i <= m; i++)
{
int pos;
scanf("%d", &pos);
for (int p = pos; !v[p]; p = fa[p])
{
v[p] = 1;
Tree_wei++;
}
farpos = wei[farpos] > wei[pos] ? farpos : pos;
printf("%d\n", Tree_wei * 2 - wei[farpos]);
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)