题目解析：

T1：Peculiar apple-tree

题意：给定一棵以 1 为根的树，每个节点初始有一个苹果，苹果每秒向父节点移动一层，到达根节点时被收集，且同一时刻同一节点的苹果会两两湮灭（偶数个全灭，奇数个剩1个），求最终根节点能收集到的苹果总数。 思路：遍历，统计在同一个深度上有多少个节点，如果是偶数，计数的变量清零，如果是奇数就会剩下一个节点，那么ans++ 公式：dep[i] = dep[p] + 1 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dep[N]; 
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    dep[1] = 0; 
    for (int i = 2; i <= n; i++) 
    {
        int p;
        cin >> p;
        dep[i] = dep[p] + 1; 
    }
    int cnt[N] = {0};
    for (int i = 1; i <= n; i++) 
    {
        cnt[dep[i]]++; 
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) 
    { 
        if (cnt[i] % 2 == 1) 
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

T2：Kefa and Park

题意:给定一棵以 1 为根的树，部分节点上有猫。餐厅全部位于叶子节点上。Kefa 从根节点出发前往餐厅，如果从根节点到某个叶子节点的路径上，出现了连续超过 $m$ 个有猫的节点，他就会放弃前往。要求计算 Kefa 最终能够成功到达的餐厅数量。

思路： 在从根节点向叶子节点遍历的过程中，我们需要实时记录当前路径上连续有猫的节点数量。 如果当前节点有猫，连续猫的数量 = 父节点的连续猫数量 + 1。 如果当前节点没有猫，连续猫的数量直接清零。 在遍历过程中，一旦发现当前节点的连续猫数量已经大于 $m$，说明这条路径已经不符合条件。此时无需继续向下遍历该分支，直接返回， 当遍历到达叶子节点时，说明 Kefa 成功到达了餐厅，此时将最终答案加 1。 因为输入的是无向边，建图时需要双向连边。在 DFS 遍历时，需要记录父节点，防止遍历过程中走回头路。 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N]; 
int a[N];        
int n, m;
int ans = 0;   
void dfs(int u, int p, int cnt) 
{
 
    if (cnt > m) return;    
    bool oof = true;
    for (int v : g[u]) 
    {
        if (v != p) 
        {
            oof = false;
            break;
        }
    }
    if (oof) 
    {
        ans++;
        return; 
    }
    for (int v : g[u]) 
    {
        if (v == p) continue;
        if (a[v] == 1) 
        {
            dfs(v, u, cnt + 1);
        } 
        else 
        {
            dfs(v, u, 0);
        }
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) 
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, -1, a[1]);
    cout << ans << endl;
    return 0;
}

T3：Cut 'em all!

题意： 思路： 代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> g[N]; 
int n;
int ans = 0;      
int dfs(int u, int p)
{
    int s = 1; 
    
    for (int v : g[u]) 
    {
        if (v == p) continue;
        s += dfs(v, u);       
    }
    if (s % 2 == 0 && p != -1) 
    {
        ans++;
        return 0; 
    }
    
    return s; 
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    if (n % 2 == 1) 
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < n - 1; i++) 
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}

T4：Decorate Apple Tree

题意： 思路： 代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> p(n + 1, 0);
    vector<int> c(n + 1, 0);
    for(int u = 2; u <= n; u++)
    {
        cin >> p[u];
        ++c[p[u]];
    }
    vector<int> f(n + 1, 0);
    for(int u = n; u >= 1; u --)
    {
        if(c[u] == 0) f[u] = 1;
        if(u != 1) f[p[u]] += f[u];
    }
    sort(f.begin(), f.end());
    for(int i = 1; i <= n; i++)
    {
        cout << f[i] << " ";
    }
    return 0; 
}

T5：Military Problem

题意： 思路： 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, q;
vector<int> g[N];   
vector<int> s;      
int in[N], out[N];  
bool vis[N];
int ti = 0;       
void dfs(int root) 
{
    stack<int> st;
    st.push(root);
    while (!st.empty()) 
    {
        int u = st.top();
        st.pop();
        
        if (vis[u]) 
        {
            out[u] = ti;
        } 
        else 
        {
            in[u] = ++ti;
            s.push_back(u);
            vis[u] = true;
            st.push(u);
            vector<int> temp = g[u];
            reverse(temp.begin(), temp.end());
            for (int v : temp) 
            {
                st.push(v);
            }
        }
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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());
    }
    dfs(1);
    while (q--) 
    {
        int u, k;
        cin >> u >> k;
        int si = out[u] - in[u] + 1;
        if (k > si) 
        {
            cout << -1 << '\n';
        } 
        else 
        {
            cout << s[in[u] + k - 2] << '\n';
        }
    }
    
    return 0;
}

T6：Timofey and a tree

题意： 思路： 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int c[N];
vector<int> g[N];
bool ch(int root) 
{
    stack<pair<int, int>> st; 
    st.push({root, -1});
    while (!st.empty()) 
    {
        int u = st.top().first; 
        int pa = st.top().second; 
        st.pop();
        for (int v : g[u]) 
        {
            if (v == pa) continue;
            if (c[v] != c[u] && u != root) 
            {
                return false;
            }
            st.push({v, u});
        }
    }
    return true;
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; 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];
    } 
    int u = -1, v = -1;
    for (int i = 1; i <= n; i++) 
    {
        for (int j : g[i]) 
        {
            if (c[i] != c[j]) 
            {
                u = i;
                v = j; 
                break;
            }
        }
        if (u != -1) break;
    }
        if (u == -1) 
    {
        cout << "YES" << endl << 1 << endl; 
        return 0;
    }
    if (ch(u)) 
    {
        cout << "YES" << endl << u << endl;
    } 
    else if (ch(v))
    {
        cout << "YES" << endl << v << endl;
    } 
    else 
    {
        cout << "NO" << endl;
    }
    return 0;
}