**t1 **：每个节点i的苹果会在深度d[i]时刻到达根。用DFS从叶子向上合并，对每个节点统计其子树中各深度到达的苹果数量，同一深度多个苹果到达同一节点时，奇数留下1个，偶数全部湮灭（奇偶抵消）。最终根节点深度0处剩余的苹果数量即为答案。每层只传递一个苹果向上，总复杂度O(n)。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt[100005],dep[100005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    dep[1]=0;
    cnt[0]=1; // 根深度0，计数+1
    for(int i=2;i<=n;i++) {
        int p;
        cin>>p;
        dep[i]=dep[p]+1;
        cnt[dep[i]]++;
    }
    int ans=0;
    for(int i=0;i<=100000;i++) {
        if (cnt[i]%2!=0) {
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

**t2 **：从根1开始DFS，维护当前路径上连续有猫的数量。遇到有猫的节点计数加1，否则清零。若连续猫数超过m则剪枝返回。到达叶子节点（非根）且连续猫数不超过m时答案加1。DFS遍历整棵树即可统计所有合法餐厅数量。

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
vector<int> g[MAXN];
int a[MAXN];
int n,m,ans;
struct Node{
    int u,fa,con;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    queue<Node> q;
    q.push({1,-1,a[1]});
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        int u=now.u,fa=now.fa,c=now.con;
        if(c>m) continue;
        bool leaf=true;
        for(int v:g[u]){
            if(v==fa) continue;
            leaf=false;
            int nc=a[v]?c+1:0;
            q.push({v,u,nc});
        }
        if(leaf) ans++;
    }
    cout<<ans;
    return 0;
}

**t3 **：若n为奇数，无法分成偶数大小的树，输出-1。否则DFS统计每个子树的大小，若某子树大小为偶数，则可以将该子树与父节点之间的边切断，答案加1。注意根节点没有父边可切，所以根节点的子树大小即使为偶数也不计入答案。

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
vector<int> g[MAXN];
int sz[MAXN];
int n,ans;
void dfs(int u,int fa){
    sz[u]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]%2==0) ans++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    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);
    }
    if(n%2!=0){
        cout<<-1;
        return 0;
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}

**t4 **：对每个节点统计其子树中的叶子数量leaf[u]。若某节点想成为快乐节点，需要给它的所有叶子染不同颜色，因此至少需要leaf[u]种颜色。对于每个k，所有叶子数≥k的节点中所需颜色数的最大值即为答案。最终输出从1到n的答案序列。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,cnt,head[N],sz[N],p;
struct Edge{//用邻接表存图
    int v,nxt;
}e[N];
void add(int u,int v){//加边
    cnt++;
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
//DFS计算子树需要的最少颜色（子树大小）
void dfs(int u){
    if(head[u]==0) sz[u]=1;//u是叶子节点
    //邻接表遍历u的所有子节点
    for(int i=head[u];i;i=e[i].nxt){
        dfs(e[i].v);//递归计算子节点e[i].v的大小
        sz[u]+=sz[e[i].v];//累加子节点，得到u的子树大小
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>p;
        add(p,i);
    }
    dfs(1);
    sort(sz+1,sz+n+1);
    for(int i=1;i<=n;i++) cout<<sz[i]<<" ";
    return 0;
}

**t5 **：先预处理出树的DFS序，访问儿子时按编号从小到大排序以确保顺序正确。记录每个节点在DFS序中的位置和子树大小。对于查询(u,k)，若k>sz[u]则输出-1，否则答案为DFS序中从dfn[u]开始第k个位置对应的节点编号。

code

#include <bits/stdc++.h>
using namespace std;
int n,q,tot,val[200005],qry[200005],sz[200005];
vector<int> g[200005];
void dfs(int x){
    stack<pair<int,int>> st;
    st.push({x,0});
    while(!st.empty()){
        int u=st.top().first;
        int state=st.top().second;
        st.pop();
        if(state==0){
            val[u]=++tot;
            qry[tot]=u;
            sz[u]=1;
            st.push({u,1});
            for(int i=(int)g[u].size()-1;i>=0;i--){
                st.push({g[u][i],0});
            }
        }else{
            for(int i=0;i<(int)g[u].size();i++){
                sz[u]+=sz[g[u][i]];
            }
        }
    }
}
int main(){
    cin>>n>>q;
    for(int i=2,fa;i<=n;i++){
        cin>>fa;
        g[fa].push_back(i);
    }
    dfs(1);
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<(sz[x]>=y?qry[val[x]+y-1]:-1)<<'\n';
    }
    return 0;
}

**t6 **：先统计整棵树中有多少条边连接了不同颜色的节点（即异色边）。若选中某个节点作为根，去掉该节点后，所有子树如果都是单色的，则说明所有异色边都必须与该节点相邻。因此，检查每个节点，若所有异色边都连接到该节点，则该节点就是答案；否则无解。

code

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
vector<pair<int,int>> edges;
int color[N];
bool check(int root){
    for(auto [u,v]:edges) {
        if(color[u]!=color[v]&&u!=root&&v!=root){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        edges.push_back({u,v});
    }
    for(int i=1;i<=n;i++) cin>>color[i];
    vector<int> bad;
    for(auto [u,v]:edges){
        if(color[u]!=color[v]){
            bad.push_back(u);
            bad.push_back(v);
        }
    }
    if(bad.empty()){
        cout<<"YES\n1";
        return 0;
    }
    int c=bad[0];
    if(check(c)){
        cout<<"YES\n"<<c;
        return 0;
    }
    for(int x:bad){
        if(check(x)){
            cout<<"YES\n"<<x;
            return 0;
        }
    }
    cout<<"NO";
    return 0;
}