想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

问题描述

真题来源：树上搜索

感兴趣的同学可以如此编码进去进行练习提交

 c++满分题解：

<code>#include <bits/stdc++.h>

using namespace std;

inline long long read()

{

long long x = 0, f = 1;

char c = getchar();

while (c < '0' || c > '9')

{

if (c == '-') f = -1;

c = getchar();

}

while ( c >= '0' && c <= '9')

{

x = x * 10 + c - '0';

c = getchar();

}

return x * f;

}

struct Node

{

long long Weight;

long long WeightSum;

long long Index;

bool IsOut;

Node* Child, * Brother, * Above, * LastChild, * PrevBrother;

Node(long long Weigh, long long i) : Weight(Weigh), Child(nullptr), LastChild(nullptr), Above(nullptr), Brother(nullptr), WeightSum(Weigh), PrevBrother(nullptr), Index(i) {}

};

Node* Nodes[2010];

void LinkNode(Node* Parent, Node* Child)

{

if (!Parent || !Child) return;

Child->Above = Parent;

if (!Parent->Child)

{

Parent->Child = Child;

Parent->LastChild = Child;

return;

}

Parent->LastChild->Brother = Child;

Child->PrevBrother = Parent->LastChild;

Parent->LastChild = Child;

}

long long AccWeights(Node* CurRoot)

{

if (!CurRoot) return 0;

CurRoot->WeightSum = CurRoot->Weight;

Node* CurNode = CurRoot->Child;

while (CurNode)

{

CurRoot->WeightSum += AccWeights(CurNode);

CurNode = CurNode->Brother;

}

return CurRoot->WeightSum;

}

bool HasTarIndex(Node* Root, long long Tar)

{

if (!Root) return 0;

else if (Root->Index == Tar) return 1;

Node* CurNode = Root->Child;

while(CurNode)

{

if (HasTarIndex(CurNode, Tar)) return 1;

CurNode = CurNode->Brother;

}

return 0;

}

long long RemovedParents[2010]{-1}, RemovedChilds[2010]{-1};

long long RemovedPairs = 0;

void RemoveNode(Node* TarNode)

{

if (!TarNode) return;

if (!TarNode->PrevBrother) TarNode->Above->Child = TarNode->Brother;

else TarNode->PrevBrother->Brother = TarNode->Brother;

if (!TarNode->Brother) TarNode->Above->LastChild = TarNode->PrevBrother;

else TarNode->Brother->PrevBrother = TarNode->PrevBrother;

TarNode->Above = nullptr;

TarNode->Brother = nullptr;

TarNode->PrevBrother = nullptr;

}

void ReBuild()

{

for (long long i = 0; i < RemovedPairs; ++i) LinkNode(Nodes[RemovedParents[i]], Nodes[RemovedChilds[i]]);

RemovedPairs = 0;

}

long long GetDelta(Node* TarNode, long long& CurTotalWeight)

{

if(!TarNode) return 114514;

else if (!TarNode->Above) return TarNode->WeightSum;

return abs(CurTotalWeight - 2 * TarNode->WeightSum);

}

long long CurMin = 0, CurIdx = 0;

void Bianli(Node* CurRoot, long long& CurTotalWeight)

{

if (!CurRoot) return;

long long Delta = GetDelta(CurRoot, CurTotalWeight);

//cout << CurRoot->Index << ' '<<Delta<<'\n';

if (Delta < CurMin || (CurMin == Delta && CurRoot->Index < CurIdx))

{

CurMin = Delta;

CurIdx = CurRoot->Index;

}

Node* CurNode = CurRoot->Child;

while (CurNode)

{

Bianli(CurNode, CurTotalWeight);

CurNode = CurNode->Brother;

}

}

void PrintTree(Node* CurRoot)

{

if (!CurRoot) return;

cout << CurRoot->Index << '\n';

Node* CurNode = CurRoot->Child;

while (CurNode)

{

cout << '\t' << CurNode->Index << '\n';

system("pause");

CurNode = CurNode->Brother;

}

CurNode = CurRoot->Child;

while (CurNode)

{

PrintTree(CurNode);

CurNode = CurNode->Brother;

}

}

int main()

{

long long n = read(), m = read();

for (long long i = 1; i<= n; ++i) Nodes[i] = new Node(read(), i);

for (long long i = 2; i <= n; ++i) LinkNode(Nodes[read()], Nodes[i]);

long long Index = 0;

for (long long i = 1; i <= m; ++i)

{

RemovedPairs = 0;

Index = read();

Node* CurRoot = Nodes[1];

while(CurRoot->Child)

{

/*

cout << "___________________\n";

PrintTree(CurRoot);

cout << "___________________\n";

*/

long long SumWeight = AccWeights(CurRoot);

CurMin = SumWeight, CurIdx = 0;

Bianli(CurRoot, SumWeight);

cout << CurIdx << ' ';

if (HasTarIndex(Nodes[CurIdx], Index)) CurRoot = Nodes[CurIdx];

else

{

RemovedParents[RemovedPairs] = Nodes[CurIdx]->Above->Index;

RemovedChilds[RemovedPairs] = Nodes[CurIdx]->Index;

++RemovedPairs;

RemoveNode(Nodes[CurIdx]);

}

}

ReBuild();

cout << '\n';

}

for (long long i = 1; i<= n; ++i) delete Nodes[i];

}

运行结果：