本题没有传送门,就把题目写清楚吧。

碎碎念
在考场上这道题没想出来,真是寄了。一直在想LCA,然后想dfs,最短路。后面想利用树的性质,怎么都想不出。
思路
先考虑每个点都要走一次且回到起点的情况,那就是每个点往上走,每条边都要走两次。这个可以类比dfs的过程,每条边都要走到两次才能保证回到起点。
由于本题要求无需回到起点,所以用路程减去一个最大深度(最长的一条链)就是答案。

比如这个图,我要从起点1去 3 5 8 9送外卖,就可以选择以8或者9为终点,那么就是每个点往上走直到“会经过的点”的边的数量 * 2 - 最长的链,这就是答案。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9; int fa[maxn],dep[maxn]; bitset<maxn> vis;//用于标记某点是否走过 int d(int x)//记忆化搜索 { if(fa[x] == -1)return 0; else if(dep[x])return dep[x]; return dep[x] = d(fa[x]) + 1; } signed main() { int N, M;cin >> N >> M; for(int i = 1;i <= N; ++ i) { int x;scanf("%lld", &x); fa[i] = x; } for(int i = 1;i <= N; ++ i)dep[i] = d(i);//获取每个点的深度 int ans = 0, maxd = 0;//maxd记录最大深度 while(M --) { int x;scanf("%lld", &x); maxd = max(maxd, dep[x]);//更新最大深度 while(fa[x] != -1 && !vis[x]) //从x点向上直到 根 或 已经走过的点 { vis[x] = 1; x = fa[x]; ans += 2; } printf("%lld\n",ans - maxd);//输出答案 } return 0; }
Comments NOTHING