DFS 树上搜索 T3 思维 #todo 龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……
看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。
输入格式:
输入第一行是两个数 和 ，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。
接下来首先是一行 个数，第 个数表示第 个点的双亲节点的编号。节点编号从 到 ，外卖站的双亲编号定义为 。
接下来有 行，每行给出一个新增的送餐地点的编号 。保证送餐地点中不会有外卖站，但地点有可能会重复。
为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 ，且从外卖站出发可以访问到所有地点。
注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。
输出格式:
对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。
输入样例:
7 4
-1 1 1 1 2 2 3
5
6
2
4输出样例:
2
4
4
6思路
光看题目有点难整, 做完样例后可以发现, 当前查询点的总路径就等于所有走过的路径x2 - 当前最深路径。
对于一个新加的点, 求它加入后对走过路径增加的个数时, 只让其往上走父节点, 直到遇见根或者以前走过的节点。
先用DFS求出树上每个点的深度, 然后处理查询即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int d[N];
bool st[N];
vector<int> g[N];
int n, m, root;
void dfs(int u)
{
for (auto &i : g[u])
{
d[i] = d[u] + 1;
dfs(i);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
if (t == -1)
root = i;
else
f[i] = t, g[t].push_back(i);
}
dfs(root);
int maxv = 0, res = 0;
while (m--)
{
int t;
cin >> t;
if (st[t])
cout << res - maxv << endl;
else
{
maxv = max(maxv, d[t]);
do
{
// cout << t << " " << res << endl;
st[t] = true;
res += 2, t = f[t];
} while (t != root && !st[t]);
cout << res - maxv << endl;
}
}
return 0;
}