自动搬运

查看原文

来自洛谷，原作者为

	MingDynasty 最后在线时间:2025.8.23 21:03|team/76415出题组|开局一个碗,结局一根绳|坐标你猜|小升初蒟蒻,欢迎吊打|5天内2小号互关(大号paste/lb3d6tr9),可提醒,不可炸铃接龙|题解不懂私|主页article/hu9a8skr

搬运于2025-08-24 23:14:33，当前版本为作者最后更新于2025-04-24 12:11:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

可以看成树形 dp。

题目思路：

我们从根节点遍历，每次记录当前的节点和它的父亲，递归下去直到叶子节点，再回溯上来根据当前节点的编号是否是 2 的倍数来修改 dp 数组的值就行。最终我们每一个节点结果就是当前节点对 2 取余作为第二维，节点编号为第一维的 dp 值。

时间复杂度 $O(n)$。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,a,dp[222222][2];
vector<int> edge[222222]; 
inline void dfs(int u,int fa){
	dp[u][u%2]++;
	for(auto v:edge[u]){
		if(v==fa) continue;
		dfs(v,u);
		dp[u][0]+=dp[v][0];
		dp[u][1]+=dp[v][1];
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=2;i<=n;i++){
    	cin>>a;
		edge[i].push_back(a);
		edge[a].push_back(i);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++) cout<<dp[i][i%2]<<'\n';
	return 0;
}

祝通过！