Arbre ! (Corrigé)

Solution

Appelons un nœud une feuille s'il a un degré de $1$. Soit $L$ le nombre total de feuilles dans l'arbre.

Racinez l'arbre au niveau $1$. Pour chaque nœud $v$, soit $s[v]$ le nombre de feuilles à l'intérieur du sous-arbre de $v$ (par rapport à cette racine). Nous pouvons calculer $s[\cdot ]$ par un DFS :

Considérons une arête quelconque $(p,v)$ où $p$ est le parent de $v$. Si nous coupons cette arête, deux composants apparaissent :

- Le côté $v$ a $s[v]$ feuilles, mais le degré de $v$ diminue de $1$. Un nœud devient une feuille si et seulement si son degré était $2$, et une feuille cesse d'être une feuille si et seulement si son degré était $1$. Par conséquent, le nombre de feuilles du côté $v$ après la coupure est

- Le côté $p$ a L-s[v] feuilles, et $p$ perd une arête incidente, donc son degré diminue également de $1$. Ainsi, le nombre de feuilles du côté $p$ après la coupure est

Une arête est équilibrée si et seulement si A=B. Nous pouvons calculer L=s[1] à partir du premier DFS, puis dans un second DFS sur les arêtes parent-enfant, tester l'égalité ci-dessus et compter combien de fois elle est vérifiée.

Esquisse de correction

Couper $(p,v)$ change le statut de feuille uniquement aux extrémités $p$ et $v$ (tout le monde garde le même degré), donc ajuster par +[\deg=2]-[\deg=1] est à la fois nécessaire et suffisant. Puisque $s[v]$ et L-s[v] comptent les feuilles strictement à l'intérieur de chaque côté avant de considérer les changements de degré des extrémités, A=B caractérise exactement les arêtes équilibrées.

Complexité $\mathcal{O}(n)$ par test (deux traversées 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;
}