/* * * ^v^ * */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long int; using ld = long double; #define iamtefu ios_base::sync_with_stdio(false); cin.tie(0); #define fl(i,a,n) for (ll i{a}; i=a; i--) #define ty int _; for(cin>>_; _--;) #define print(a) for(auto ele:a){cout< inline bool chmax(L &a, R b){if (a inline bool chmin(L &a, R b){if (a>b){a=b;return 1;}return 0;} template ostream& operator<<(ostream &fout, const pair &p){ fout<<"{"< ostream& operator<<(ostream &fout, const tuple &p){ auto &[l, r, u] = p; fout<<"{"< ostream& operator<<(ostream &fout, const vector &v){ for (auto &x:v){ fout< ostream& operator<<(ostream &fout, const set &st){ for (auto &x:st){ fout< ostream& operator<<(ostream &fout, const multiset &st){ for (auto &x:st){ fout< ostream& operator<<(ostream &fout, const map &mp){ fout<<"["; for (auto &[x,y]:mp){ fout<>n; vector > ed(n+1); fl(i,0,n-1){ ll u, v; cin>>u>>v; ed[u].push_back(v); ed[v].push_back(u); } vector vis(n+1); vector > dp(n+1, vector (4, 0)); auto dfs=[&](const auto &self, ll i)->void{ vis[i]++; for (auto x:ed[i]){ if (!vis[x]){ self(self, x); fl(k,0,3){ dp[i][k+1]+=dp[x][k]; } } } dp[i][0]=1; }; dfs(dfs, 1); ll ans = 0; auto df=[&](const auto &self, ll i)->void{ vis[i]++; fl(j,1,4){ ans+=dp[i][j]; } for (auto x:ed[i]){ if (!vis[x]){ auto pr = dp[x], pr1 = dp[i]; fl(k,0,3){ dp[i][k+1]-=dp[x][k]; } fl(k,0,3){ dp[x][k+1]+=dp[i][k]; } self(self, x); swap(dp[i], pr1); swap(dp[x], pr); } } }; fill(vis.begin(), vis.end(), 0); df(df, 1); cout<(t2-t1).count(); ti*=1e-6; cerr<<"Time: "<