¡Árbol! (Editorial)

Solución

Llamamos a un nodo una hoja si tiene grado $1$. Sea $L$ el número total de hojas en el árbol.

Raíz el árbol en $1$. Para cada nodo $v$, sea $s[v]$ el número de hojas dentro del subárbol de $v$ (con respecto a esta raíz). Podemos calcular $s[\cdot ]$ mediante un DFS:

Considera cualquier arista $(p,v)$ donde $p$ es el padre de $v$. Si cortamos esta arista, aparecen dos componentes:

- El lado $v$ tiene $s[v]$ hojas, pero el grado de $v$ disminuye en $1$. Un nodo se convierte en hoja si y solo si su grado era $2$, y una hoja deja de ser hoja si y solo si su grado era $1$. Por lo tanto, el conteo de hojas en el lado $v$ después del corte es

- El lado $p$ tiene L-s[v] hojas, y $p$ pierde una arista incidente, por lo que su grado también disminuye en $1$. Así, el conteo de hojas en el lado $p$ después del corte es

Una arista es equilibrada si A=B. Podemos calcular L=s[1] desde el primer DFS, luego en un segundo DFS sobre las aristas padre-hijo, probar la igualdad anterior y contar cuántas veces se cumple.

Esquema de Corrección

Cortar $(p,v)$ cambia el estado de hoja solo en los extremos $p$ y $v$ (todos los demás mantienen el mismo grado), por lo que ajustar por +[\deg=2]-[\deg=1] es tanto necesario como suficiente. Dado que $s[v]$ y L-s[v] cuentan hojas estrictamente dentro de cada lado antes de considerar los cambios de grado de los extremos, A=B caracteriza exactamente las aristas equilibradas.

Complejidad $\mathcal{O}(n)$ por prueba (dos recorridos DFS).

#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;
}