fork download 
  1.     #include<bits/stdc++.h>
  2.     typedef long long ll;
  3.     typedef unsigned long long ull;
  4.     typedef long double ld;
  5.     typedef double db;
  6.     #define endl "\n"
  7.     #define ss second
  8.     #define ff first
  9.     #define all(x) (x).begin() , (x).end()
  10.     #define pb push_back
  11.     #define vi vector<int>
  12.     #define vii vector<pair<int,int>>
  13.     #define vl vector<ll>
  14.     #define vll vector<pair<ll,ll>>
  15.     #define pii pair<int,int>
  16.     #define pll pair<ll,ll>
  17.     #define pdd  pair<double,double>
  18.     #define vdd  vector<pdd>
  19.     #define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  20.     using namespace std;
  21.  
  22.     #define int ll
  23.  
  24.     ////////////////////Only Clear Code//////////////////////////
  25.  
  26.     void init(){
  27.         #ifndef ONLINE_JUDGE
  28.  
  29.     freopen("input.txt", "r", stdin);
  30.  
  31.     freopen("output.txt", "w", stdout);
  32.  
  33.     #endif // ONLINE_JUDGE
  34.     }
  35.     const int mx = 2e5+5;
  36.     const int LOG = 22;
  37.     const int inf = 1e9;
  38.     const ll mod = 998244353;
  39.     const int sq = 300;
  40.  
  41.     vi graph[mx];
  42.     ll n;
  43.     ll sz[mx];
  44.  
  45.     ll nb_leafs[mx];
  46.  
  47.     bool leaf[mx];
  48.     ll totwin = 0, totleafs = 0;
  49.     bool winning[mx];
  50.     ll ans = 0;
  51.     ll nbwin[mx];
  52.  
  53.     void dfs(int node, int p){
  54.         sz[node] = 1;
  55.         nb_leafs[node] = 0;
  56.         for(int adj : graph[node]){
  57.             if(adj == p)continue;
  58.             dfs(adj, node);
  59.             sz[node] += sz[adj];
  60.             nb_leafs[node] += nb_leafs[adj];
  61.         }
  62.         if(sz[node] == 1){
  63.             // leaf
  64.             nb_leafs[node] = 1;
  65.             leaf[node] = 1;
  66.         }
  67.  
  68.     }
  69.  
  70.     void pre(int node, int p = -1){
  71.         if(leaf[node])return;
  72.         nbwin[node] = winning[node];
  73.         for(int adj : graph[node]){
  74.             if(adj == p)continue;
  75.             pre(adj, node);
  76.             nbwin[node] += nbwin[adj];
  77.         }
  78.     }
  79.  
  80.     void dfs1(int node, int p = -1){
  81.         if(leaf[node])return;
  82.         for(int adj : graph[node]){
  83.             if(adj == p)continue;
  84.             dfs1(adj, node);
  85.         }
  86.         // go up
  87.         // p should be up
  88.         if(p != -1 && winning[p]){
  89.             ans += n - sz[node] - (totwin - nbwin[node]) - (totleafs - nb_leafs[node]);
  90.         }
  91.         // look down
  92.         for(int adj : graph[node]){
  93.             if(adj == p)continue;
  94.             if(winning[adj]){
  95.                 ans += sz[adj] - nbwin[adj] - nb_leafs[adj];
  96.             }
  97.         }
  98.     }
  99.  
  100.     void runcase(){
  101.         cin >> n;
  102.         ans = 0;
  103.         totwin = 0;
  104.         totleafs = 0;
  105.         for(int i = 1; i <= n;i++){
  106.             graph[i].clear();
  107.             sz[i] = 0;
  108.             nb_leafs[i] = 0;
  109.             winning[i] = leaf[i] = 0;
  110.             nbwin[i] = 0;
  111.         }
  112.         for(int i = 1; i < n;i++){
  113.             int u, v;cin >> u >> v;
  114.             graph[u].pb(v);
  115.             graph[v].pb(u);
  116.         }
  117.         int root = -1;
  118.         for(int i = 1; i <= n;i++){
  119.             if(graph[i].size() >= 2)root = i;
  120.         }
  121.         if(root == -1){
  122.             cout << 0 << endl;
  123.             return;
  124.         }
  125.         dfs(root, root);
  126.         ans = nb_leafs[root] * (n-nb_leafs[root]);
  127.         for(int i = 1; i <= n;i++){
  128.             for(int adj : graph[i]){
  129.                 winning[i] |= leaf[adj];
  130.             }
  131.             if(leaf[i])winning[i] = 0;
  132.             totwin += winning[i];
  133.             totleafs += leaf[i];
  134.         }
  135.         pre(root);
  136.         dfs1(root);
  137.         cout << ans << endl;
  138.     }
  139.  
  140.     int32_t main(){
  141.         init();
  142.         speed;
  143.         int t = 1;
  144.         cin >> t;
  145.         while(t--){
  146.             runcase();
  147.         }
  148.     }
  149.  
  150.     /*
  151.         NEVER GIVE UP!
  152.         DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
  153.         Your Guide when stuck:
  154.         - Continue keyword only after reading the whole input
  155.         - Don't use memset with testcases
  156.         - Check for corner cases(n=1, n=0)
  157.         - Check where you declare n(Be careful of declaring it globally and in main)
  158.     */
Success #stdin #stdout 0.01s 10280KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/fMlmuH
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!