Ağac! (Həll təhlili)

Həll

Bir düyünü yarpaq adlandırırıq əgər onun dərəcəsi $1$-dirsə. $L$ ağacdakı yarpaqların ümumi sayını göstərsin.

Ağacı $1$-də kökləyin. Hər bir düyün $v$ üçün, $s[v]$ düyünün alt ağacında (bu kök nəzərə alınmaqla) olan yarpaqların sayını göstərsin. $s[\cdot ]$-ni bir DFS ilə hesablaya bilərik:

Hər hansı bir kənarı $(p,v)$ nəzərdən keçirin, burada $p$ $v$-nin valideynidir. Bu kənarı kəsdikdə iki komponent yaranır:

- $v$-tərəfi $s[v]$ yarpağa malikdir, amma $v$-nin dərəcəsi $1$-ə düşür. Bir düyün yarpaq olur əgər onun dərəcəsi $2$ idisə, və bir yarpaq yarpaq olmağı dayandırır əgər onun dərəcəsi $1$ idisə. Buna görə də, kəsildikdən sonra $v$-tərəfdəki yarpaqların sayı

- $p$-tərəfi L-s[v] yarpağa malikdir, və $p$ bir kənar itirir, buna görə də onun dərəcəsi də $1$-ə düşür. Beləliklə, kəsildikdən sonra $p$-tərəfdəki yarpaqların sayı

Bir kənar balanslıdır əgər A=B. Biz L=s[1]-i birinci DFS-dən hesablaya bilərik, sonra valideyn-uşaq kənarları üzərində ikinci DFS-də yuxarıdakı bərabərliyi yoxlayıb neçə dəfə baş verdiyini sayarıq.

Düzgünlük eskizi

$(p,v)$ kəsilməsi yalnız ucları $p$ və $v$-də yarpaq statusunu dəyişir (digər hər kəs eyni dərəcəni saxlayır), buna görə də +[\deg=2]-[\deg=1] ilə düzəliş etmək həm zəruri, həm də kifayətdir. Çünki $s[v]$ və L-s[v] kəsilmədən əvvəl hər tərəfdəki yarpaqları dəqiq sayır, A=B balanslı kənarları dəqiq xarakterizə edir.

Komplekslik $\mathcal{O}(n)$ hər test üçün (iki DFS keçidi).

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