A.Peculiar apple-tree

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF930A

题意：这是一棵以1为根的树，每个节点初始有1个苹果。所有苹果同时向根节点1滚动，每秒移动一条边。湮灭规则：同一时刻在同一节点的苹果两两湮灭（偶数全灭，奇数剩1）。问：最终根节点1能收集到多少个苹果？

思路：深度相同的节点，苹果到达根节点的时间相同。深度d的节点→第d秒到达根节点同一深度的苹果同时到达→在根节点湮灭，不同深度的苹果不同时间到达→互不影响

#include<bits/stdc++.h>
using namespace std;
int zx[100010],cnt[100010];
vector<int>b[100010];
int main(){
	int n,ans=0;
	cin>>n;
	zx[1]=1;
	for(int i=2;i<=n;i++){
		int a;
		cin>>a;
		b[a].push_back(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<b[i].size();j++){
			zx[b[i][j]]=zx[i]+1;
		}
		cnt[zx[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(cnt[i]%2==1)ans++;
	}
	cout<<ans;
	return 0;
}

B.Kefa and Park

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF580C

题意：以1为根的有根树，每个节点有猫(1)或没猫(0)。从根节点1到某个叶子节点的路径上，连续出现猫的节点数量不能超过 m。求：满足条件的叶子节点数量。

思路：从根节点1开始DFS，维护当前路径上连续有猫的节点数量：当前节点有猫：cnt=cnt+1当前节点没猫：cnt=0,如果 cnt>m：剪枝，不再往下走,当到达叶子节点时，如果cnt<=m，答案+1。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[100005];
vector<int>g[100005];
void dfs(int u,int fa,int c)
{
	if(c>m)return;
	int f=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v!=fa){
			f=0;
			int nxt;
			if(a[v]) nxt=c+1;
			else nxt=0;
			dfs(v,u,nxt);
		}
	}
	if(f==1&&u!=1) ans++;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0,a[1]);
	cout<<ans;
	return 0;
}

C.Cut 'em all!

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF982C

题意：有一棵有n个节点的树,删去最多的边使得每一棵森林中的树的大小为偶数，并输出删去的边数思路：如果n是奇数：不可能分成若干个偶数大小的连通块（偶数之和还是偶数），输出-1。如果n是偶数：一定存在方案。从叶子节点向上 DFS，统计每个节点的子树大小。如果某个节点的子树大小是偶数，就可以把该节点和父节点之间的边删掉：这个子树本身可以分割成偶数大小的连通块（递归成立）剩下的部分大小=n-偶数=偶数所以删掉这条边不影响其他部分，答案=所有大小为偶数的子树数量（不包括整棵树）

#include<bits/stdc++.h>
using namespace std;
int n,ans,zx[100005];
vector<int>g[100005];
void dfs(int u,int fa)
{
	zx[u]=1;
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]!=fa){
			dfs(g[u][i],u);
			zx[u]+=zx[g[u][i]];
			if(zx[g[u][i]]%2==0)ans++;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if(n%2==1){
		cout<<-1;
		return 0;
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

D.Decorate Apple Tree

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF1056D

题意：有一棵以1为根的有根树，叶子节点可以染成任意颜色。快乐节点：该节点的子树中，所有叶子节点的颜色都互不相同。对于每个 k（1 到 n），问：要让快乐节点的数量 ≥ k，最少需要多少种不同的颜色？

思路：因为只要颜色总数 ≥ 叶子数，就可以给每个叶子分配不同颜色。反之：如果 leaf[u] > C，根据鸽巢原理，必有叶子颜色相同，u 不可能快乐。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100005];
int n,ye[100005],cnt[100005],zx[100005];
void dfs(int u)
{
	if(g[u].size()==0){
		ye[u]=1;
		return;
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		dfs(v);
		ye[u]+=ye[v];
	}
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int p;
		cin>>p;
		g[p].push_back(i);
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		cnt[ye[i]]++;
	}
	for(int i=1;i<=n;i++){
		zx[i]=zx[i-1]+cnt[i];
	}
	int ans=1;
	for(int k=1;k<=n;k++){
		while(ans<=n&&zx[ans]<k)ans++;
		cout<<ans<<" ";
	}
	return 0;
}

E.Military Problem

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF1006E

题意：给定一棵以1为根的有根树，每个节点有若干子节点，子节点按编号从小到大的顺序访问。 查询：对于每个查询(u,k)，从节点u开始进行DFS，第k个访问到的节点是谁？

思路:从根节点1开始做一次完整的DFS，得到一个DFS序（先序遍历顺序）。对于任意节点u：从u开始的DFS访问顺序=DFS序中从 pos[u] 开始的一段连续区间，区间长度=sz[u]（子树大小）

#include<bits/stdc++.h>
using namespace std;
vector<int>g[200005];
int zx[200005], pos[200005], sz[200005],st[200005], it[200005];
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		int p;
		cin>>p;
		g[p].push_back(i);
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(), g[i].end());
	}
	int tot=0, top=0;
	st[++top]=1;
	while(top){
		int u=st[top];
		if(!pos[u]){
			pos[u]=++tot;
			zx[tot]=u;
			sz[u]=1;
		}
		if(it[u] < (int)g[u].size()){
			int v=g[u][it[u]++];
			st[++top]=v;
		}else{
			top--;
			if(top){
				sz[st[top]] += sz[u];
			}
		}
	}
	while(q--){
		int u,k;
		cin>>u>>k;
		if(k>sz[u]) cout<<-1<<"\n";
		else cout<<zx[pos[u]+k-1]<<"\n";
	}
	return 0;
}

F.Timofey and a tree

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5b3527b0fb7a5b2e6fd517/problem/CF763A

题意：给定一棵树，每个节点有颜色。选择一个节点作为根，使得所有子树（不包含整棵树）内部的颜色都相同（即没有颜色混合）。求是否存在这样的节点，如果有输出任意一个。

思路：遍历所有边，找出颜色不同的边，统计每条异色边的两个端点出现的次数，如果有某个节点出现在所有异色边中（出现次数=异色边总数），则该节点是合法根，如果不存在，输出 NO

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100005];
int c[100005],cnt[100005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	int zx=0;
	for(int u=1;u<=n;u++){
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(c[u]!=c[v]){
				zx++;
				cnt[u]++;
				cnt[v]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(cnt[i]==zx){
			cout<<"YES\n"<<i;
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}