★实验任务
可怜的 Bibi 刚刚回到家，就发现自己的手机丢了，现在他决定回头去搜索 自己的手机。 现在我们假设 Bibi 的家位于一棵二叉树的根部。在 Bibi 的心中，每个节点 都有一个权值 x，代表他心中预感向这个节点走可能找回自己手机的程度（虽然 他的预感根本不准）。当 Bibi 到达一个节点时，如果该节点有未搜索过的儿子节 点，则 Bibi 会走向未搜索过的儿子节点进行搜索，否则就返回父亲节点。如果 某节点拥有两个未搜索过的儿子节点，Bibi 会选择先搜索权值大的儿子节点。 假设 Bibi 从一个节点到达另一个节点需要 1 单位时间，搜索节点的时间忽 略不计，那么请问当 Bibi 的手机位于编号为 k 的节点时，他需要多少单位时间 才能找到手机。
★数据输入
输入第一行为一个正整数 n（1≤n≤100000）表示树的节点数目，树根的编号 总是为 1。 接下来 n-1 行，每行两个正整数 p，x（1≤x≤100）。代表编号为 i 的节点的父 亲节点 p 和权值 x。这里的 i 从 2 依次数到 n。数据保证输入的 p 小于当前的 i， 且互为兄弟的两个节点的权值 x 不同。 第 n+1 行一个整数 m（1≤m≤n）， 表示询问组数。 第 n+2 行有 m 个整数，每个整数 ki（1≤ki≤n）代表该组询问中手机的位置。
★数据输出
输出 m 行，每行一个整数，代表 Bibi 找到手机需要花费的单位时间数量。
测试样例
输入：
3
1 20
1 30
3
1 2 3
输出：
0
3
1
解题过程：
暂时个人认为二叉树其实更好实现，因为之前对于儿子个数不确定的树需要用链表很不熟悉（不过现在感觉用动态数组vector可以好多了），而二叉树每个节点有两个儿子实现就比较简单；
解题思路：
通过深搜的方法实现，用递归回溯的思想对走的步数（即时间）进行计算并同步存储，这题还需要我们同时对每个节点的时间存储，因为访问的次数可能会很多容易超时。
代码：
给我帮助的同学的代码（通过vector写）：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#define MAX_SIZE 100005
using namespace std;
struct node
{
int quan, bu;
bool vis;
}tree[MAX_SIZE];
vector <int> v[MAX_SIZE];
int cnt = -1;
int n;
void dfs(int ge)
{
cnt++;
if (tree[ge].vis == false)
{
tree[ge].vis = true;
tree[ge].bu = cnt;
}
if (!v[ge].empty())
{
vector<int>::iterator it;
for (it = v[ge].begin(); it != v[ge].end(); it++)
dfs(*it);
}
cnt++;
}
int main()
{
int i, j;
scanf("%d", &n);
for (i = 1; i <= n; i++)
v[i].clear();
for (i = 2; i <= n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
tree[i].quan = b;
tree[i].vis = false;
v[a].push_back(i);
}
for (i = 1; i <= n; i++)
{
if (!v[i].empty() && v[i].size()>1)
{
if (tree[v[i][0]].quan<tree[v[i][1]].quan)
swap(v[i][0], v[i][1]);
}
}
dfs(1);
int m;
scanf("%d", &m);
for (i = 1; i <= m; i++)
{
int a;
scanf("%d", &a);
printf("%d
", tree[a].bu);
}
// system("pause");
return 0;
}
之后对我之前用数组实现的代码的改进实现：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define MAX_SIZE 100005
using namespace std;
int cnt = -1;
struct Node
{
int ele;
int son1, son2;
int vis;
int ste;
}node[MAX_SIZE];
void dfs(int loca)
{
cnt++;
if (node[loca].vis == 0)
{
node[loca].vis = 1;
node[loca].ste = cnt;
}
if (node[node[loca].son1].vis == 0 && node[loca].son1 != 0)
{
dfs(node[loca].son1);
cnt++;
}
if (node[node[loca].son2].vis == 0 && node[loca].son2 != 0)
{
dfs(node[loca].son2);
cnt++;
}
}
int main()
{
int n, i, j;
cin >> n;
for (i = 2; i <= n; i++)
{
int father;
cin >> father >> node[i].ele;
if (node[father].son1 == 0)node[father].son1 = i;
else
{
if (node[node[father].son1].ele < node[i].ele)
{
node[father].son2 = node[father].son1;
node[father].son1 = i;
}
else node[father].son2 = i;
}
node[i].vis = 0;
}
dfs(1);
int m;
cin >> m;
for (i = 1; i <= m; i++)
{
int tmp;
cin >> tmp;
cout << node[tmp].ste << endl;
}
return 0;
}
题目收获：二叉树可以方便的通过数组实现，而树其实也不会很难，可以通过vector动态数组实现就行。