L2-043 龙龙送外卖(天梯赛)

首先这个题目正面模拟是不可能的 因为加入这个点后的改变值不好算

那就整体想 因为要到其他外卖点 所以有很多边是要走两遍的 一去一回 但是又不用再回到外卖站 不回到外卖站一定是到最远的那个

所以很清晰了 对于外卖站到每个外卖点覆盖的路径*2-最长的一条

#include 
using namespace std;

int main() { 
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, m, rt;
	cin >> n >> m;
	vector> G(n + 1);
	vector p(n + 1);
	for(int i = 1, x; i <= n; ++ i) {
		cin >> x;
		if(x == -1) rt = i;
		else {
	 		G[x].push_back(i);
			p[i] = x;
		}
	}
	vector d(n + 1);
	auto dfs = [&](auto self, int u) -> void {
		for(int &v : G[u]) {
			d[v] = d[u] + 1;
			self(self, v);
		}
	};
	d[rt] = 0;
	dfs(dfs, rt);
	vector st(n + 1);
	st[rt] = 1;
	int ans = 0, mx = 0;
	while(m -- ) {
		int x;
		cin >> x;
        mx = max(mx, d[x]);
		while(st[x] == 0) {
            st[x] = 1;
            x = p[x];
			ans ++;
		}
		cout << ans * 2 - mx << "\n";
	}

	return 0;
}