T1：

题目分析：每一层的花会同时到达1号点。求层数就是求每个点到根节点的距离（深度）。深度相同的节点数如果是奇数，ans++；如果是偶数，则不变。

#include<bits/stdc++.h>
using namespace std;
int n;
int p[100005];
int depth[100005];
int t[100005];
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>p[i];
	} 
	for(int i=1;i<=n;i++){
		depth[i]=depth[p[i]]+1;
		t[depth[i]]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(t[i]%2==1)ans++;
	}
	cout<<ans;
	return 0;
} 

T2:

题目分析：BFS时加上一个连续遇猫判断即可。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,cost;	
};
int n,m;
int a[100005];
vector<int>G[100005];
int ans;
bool vis[100005];
int main(){
	cin>>n>>m;
    if(n==1){
        cout<<1;
        return 0;
    }
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
    G[1].push_back(0);
	queue<node>q;
	if(a[1]==0)
		q.push({1,0});
	else 
		q.push({1,1});
	while(q.size()){
		int p=q.front().x;
		int c=q.front().cost;
		vis[p]=1; 
		q.pop();
		if(c<=m&&G[p].size()==1)ans++;
		if(c>m) continue;
		for(int i=0;i<G[p].size();i++){
			if(vis[G[p][i]]==0){
				int tmp=c;
				if(a[G[p][i]]==1)tmp+=1;
				else tmp=0;
				q.push({G[p][i],tmp});
			}
		}
	}
	cout<<ans;
	return 0;
} 

T3: 题目：在有n个节点的树种删一些边，使剩下的树的大小全都是偶数。 分析：若n为奇数，则-1.若n为偶数，则：对于每个点，若以他为根的子树大小为偶，则可以切割，ans++。因为切割后剩下的树的大小也绝对是偶数

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

T4: 题目：

给你一个n个结点以1为根的树，给这颗树的叶子结点任意染色，定义一个点为快乐结点当且仅当这个结点的子树上所有叶子节点颜色均不相同。求出对于1∼n中的每一个k，快乐结点数大于等于k所需要的最少颜色数。

分析：设f[u]为以u为根的子树的所需颜色的值，这个值其实就是以u为根的子树的叶子结点数量。f中所有小于等于f[u]的都可以用f[u]种颜色包括（是u根子树的子树：当然可以。在外面：轮换着用）。所以，求出f[u]再排序输出即可。

#include<bits/stdc++.h>
using namespace std;
int n;
int p[100005];
int outcnt[100005];
int w[100005];
vector<int>G[100005];
int dfs1(int x){
	if(outcnt[x]==0)return w[x]=1;
	for(int i=0;i<G[x].size();i++){
		w[x]+=dfs1(G[x][i]);
	}
	return w[x];
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		scanf("%d",&p[i]);
		G[p[i]].push_back(i);
		outcnt[p[i]]++;	
	}
	dfs1(1);
	sort(w+1,w+1+n); 
	for(int i=1;i<=n;i++)cout<<w[i]<<" ";
	return 0;
}

T5: 题目：给定一颗n个节点的树。q次询问，每次给u,k.问从u开始，DFS到的第k个是什么。DFS按从小到大来。 分析：先求出整棵树以1为起点的DFS序。以u为根的子树一定是连续的在原DFS序上的，且与其顺序一致。所以，要先求出原DFS序，再求每颗子树的大小f[u]。询问时，若f[u]\<k则-1，否则输出在原DFS序上的答案。u在原DFS序上的位置，求一个映射就出来了。

#include<bits/stdc++.h>
using namespace std;
int n,q;
int p[200005];
vector<int>G[200005];
vector<int>arr;
int weizhi[200005];
int w[200005];
bool cmp(int x,int y){
    return x>y;
}
int main(){
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		cin>>p[i];
		G[p[i]].push_back(i);
	}
    for(int i=1;i<=n;i++){
        sort(G[i].begin(),G[i].end(),cmp);
    }
	arr.push_back(0);
    stack<int>st;
    st.push(1);
    while(st.size()){
        int p=st.top();
        arr.push_back(p);
        st.pop();
        for(int i=0;i<G[p].size();i++){
            int u=G[p][i];
            st.push(u);
        }
    }
    for(int i=n;i>=1;i--){
        w[i]+=1;
        if(i!=1)w[p[i]]+=w[i];
    }
	for(int i=1;i<=n;i++)
		weizhi[arr[i]]=i;
while(q--){
	int u,k;
	cin>>u>>k;
	if(k>w[u])cout<<-1<<"\n";
	else
		cout<<arr[weizhi[u]+k-1]<<"\n";
}
	return 0;
}

T6:

题目 :对于一棵无根树，每个点都有一个颜色。选一个点作为根节点，删除根与其他所有直接与他相连的点的边。使形成的几颗子树中每一颗各自的颜色一致。

分析：若e(u,v)的c[u]!=c[\v]，则e(u,v)是一条异色边。最后，所有的异色边都要被删除。但是只能删一个点。所以要找出这样一个点，存在于所有异色边中。

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>G[100005];
int c[100005];
int p[100005];
int tot=0;
int main(){
	cin>>n;
	for(int i=1;i<=n-1;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];
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<G[i].size();j++){
			int u=G[i][j];
			if(c[i]!=c[u]){
				p[i]++;
				p[u]++;	
				tot++;
			} 
		}
	}
	for(int i=1;i<=n;i++){
		if(p[i]==tot){
			cout<<"YES"<<"\n"<<i;
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}