Tree ! (Editorial)

Solution

Call a node a leaf if it has degree $1$. Let $L$ be the total number of leaves in the tree.

Root the tree at $1$. For every node $v$, let $s[v]$ be the number of leaves inside the subtree of $v$ (with respect to this root). We can compute $s[\cdot ]$ by one DFS:

Consider any edge $(p,v)$ where $p$ is the parent of $v$. If we cut this edge, two components appear:

- The $v$-side has $s[v]$ leaves, but the degree of $v$ drops by $1$. A node becomes a leaf iff its degree was $2$, and a leaf stops being a leaf iff its degree was $1$. Therefore, the leaf count on the $v$-side after the cut is

- The $p$-side has L-s[v] leaves, and $p$ loses one incident edge, so its degree also drops by $1$. Thus the leaf count on the $p$-side after the cut is

An edge is balanced iff A=B. We can compute L=s[1] from the first DFS, then in a second DFS over parent-child edges, test the equality above and count how many times it holds.

Correctness sketch

Cutting $(p,v)$ changes leaf status only at the endpoints $p$ and $v$ (everyone else keeps the same degree), so adjusting by +[\deg=2]-[\deg=1] is both necessary and sufficient. Since $s[v]$ and L-s[v] count leaves strictly inside each side before considering endpoint degree changes, A=B exactly characterizes balanced edges.

Complexity $\mathcal{O}(n)$ per test (two DFS traversals).

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

#define int int64_t
using vi=vector<int>;

void solve(){
    int n;cin>>n;
    vector<vi> g(n+1);
    for(int i=0,u,v;i<n-1;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> s(n+1);
    vector<char> vis(n+1,0);

    auto tour= [&](auto self,int v,int p)->void{
        vis[v]=1;
        s[v]+= (int)g[v].size()==1;
        for(int u:g[v]) if(u!=p) self(self,u,v), s[v]+=s[u];
    };
    tour(tour,1,0);
    int L=s[1], ans=0;
    fill(vis.begin(),vis.end(),0);

    auto dfs= [&](auto self,int v,int p)->void{
        vis[v]=1;
        for(int u:g[v]) if(u!=p){
            int A = s[u] + ((int)g[u].size()==2) - ((int)g[u].size()==1);
            int B = L - s[u] + ((int)g[v].size()==2) - ((int)g[v].size()==1);
            ans += (A==B);
            self(self,u,v);
        }
    };
    dfs(dfs,1,0);
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; if(!(cin>>t)) return 0;
    while(t--) solve();
    return 0;
}