結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2024-09-23 20:41:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 12,747 bytes |
コンパイル時間 | 14,341 ms |
コンパイル使用メモリ | 325,784 KB |
実行使用メモリ | 13,440 KB |
最終ジャッジ日時 | 2024-09-23 20:59:38 |
合計ジャッジ時間 | 21,672 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;#pragma region Macros#ifdef ONLINE_JUDGE#define dbg(x) 0#else#define dbg(x) cout << __LINE__ << " : " << #x << " = " << (x) << endl;#endifusing ll = long long;using ull = unsigned long long;using pii = pair<int, int>;using pll = pair<ll, ll>;using plll = pair<ll, pll>;using db = double;using ld = long double;template<typename T>using vc = vector<T>;template<typename T>using vvc = vector<vc<T>>;template<typename T>using vvvc = vector<vvc<T>>;template<typename T>using vvvvc = vector<vvvc<T>>;template<class T>using vvvvvc = vector<vvvvc<T>>;template<class T>using vvvvvvc = vector<vvvvvc<T>>;template<class T>using vvvvvvvc = vector<vvvvvvc<T>>;template<class T>using vvvvvvvvc = vector<vvvvvvvc<T>>;#define rep(i,n) for(int i=0;i<(n);i++)#define drep(i,n) for(int i=(n);i>=0;i--)#define DREP(i,n,m) for(int i=(n);i>=(m);i--)#define REP(i,n,m) for(int i=n;i<(m);i++)#define fi first#define se second#define pb push_back#define eb emplace_back#define mp make_pair#define ti tuple<int,int,int>#define tl tuple<ll,ll,ll>#define mt make_tuple#define all(nAdjNhqW) (nAdjNhqW).begin(), (nAdjNhqW).end()#define rall(n) n.rbegin(),n.rend()#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}#define yn(bool) YesNo(bool)#define sz(xXJE7flj) (int)xXJE7flj.size()#define dame cout<<-1<<endl;#define bye return;#define bye0 return 0;#define vec vector#define vvi vector<vector<int>>#define vvl vector<vector<ll>>#define vvvl vector<vvl>#define vvvvl vector<vvvl>#define vi vector<int>#define vp vector<pii>#define vpl vector<pll>#define ge(vEqMgDq5,i) get<i>(vEqMgDq5)#define vl vector<ll>#define vs vector<string>#define vvvi vector<vvi>#define vb vector<bool>#define vvb vector<vector<bool>>#define vvvb vec<vvb>#define vs vector<string>#define vvs vector<vs>#define vd vector<double>#define vvd vector<vd>#define vld vector<ld>#define vvld vector<vld>#define pque priority_queue#define smpq(n) priority_queue<n,vector<n>,greater<n>>#define bipq(n) priority_queue<n, vector<n>,less<n>>#define piii pair<int,pair<int,int>>#define ednl endl#define denl endl#define Endl endl#define Yes cout<<"Yes"<<endl;#define No cout << "No"<<endl;#define OUT(n) cout<<n<<endl;#define fore(x,y) for(auto&x:y)#define nep next_permutation#define is insert#define el while(1)#define For(x,v) for(auto&x:v)#define sps ' 'const long double pi = 3.1415926535897932384626433;const int inf = (1LL << 30);const ll INF = (1LL << 62) - 1;template<typename T, typename U> inline bool chmax(T& a, U b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T, typename U> inline bool chmin(T& a, U b) { return ((a > b) ? (a = b, true) : (false)); }int zero() { return 0; }ll zerol() { return 0ll; }int plu(int a, int b) { return a + b; }int mini(int a, int b) { return min(a, b); }int maxi(int a, int b) { return max(a, b); }ll plusl(ll a, ll b) { return a + b; }ll minl(ll a, ll b) { return min(a, b); }int infi() { return inf; };ll infl() { return INF; }int dx[] = { -1,0,1,0 ,1,1,-1,-1 };int dy[] = { 0 ,1,0,-1,1,-1,1,-1 };template<class T> vector<T> sorted(vector<T>& a) { auto f = a; sort(all(f)); return f; }string sorted(string s) { sort(all(s)); return s; }template<class T>vector<T>reversed(vector<T>& a) { auto f = a; reverse(all(f)); return f; }string reversed(string s) { reverse(all(s)); return s; }template<class T> vector<T> operator++(vector<T>& v, int) { for (auto& x : v)x += 1; return v; }template<class T> vector<T> operator--(vector<T>& v, int) { for (auto& x : v) x -= 1; return v; }template<class T, class U> pair<T, U> operator++(pair<T, T>& p, int) { p.first++; p.second++; return p; }template<class T, class U> pair<T, U> operator--(pair<T, T>& p, int) { p.first--; p.second--; return p; }template<class T, class U> vector<T> operator-(vector<T> v, U s) { for (auto& x : v) x -= s; return v; }template<class T, class U> vector<T> operator-=(vector<T>& v, U s) { for (auto& x : v) x -= s; return v; }template<class T, class U> vector<T> operator+(vector<T> v, U s) { for (auto& x : v) x += s; return v; }template<class T, class U> vector<T> operator+=(vector<T>& v, U s) { for (auto& x : v) x += s; return v; }template<class T, class U> vector<T> operator*(vector<T> v, U s) { for (auto& x : v) x *= s; return v; }template<class T, class U> vector<T> operator*=(vector<T>& v, U s) { for (auto& x : v) x *= s; return v; }template<class T, class U> vector<T> operator/(vector<T> v, U s) { for (auto& x : v) x /= s; return v; }template<class T, class U> vector<T> operator/=(vector<T>& v, U s) { for (auto& x : v)x /= s; return v; }template<class T, class U, class S> pair<T, U> operator-(pair<T, U> p, S n) { p.fi -= n; p.se -= n; return p; }template<class T, class U, class S> pair<T, U> operator-=(pair<T, U>& p, S n) { p.fi -= n; p.se -= n; return p; }template<class T, class U, class S> pair<T, U> operator+(pair<T, U> p, S n) { p.fi += n; p.se += n; return p; }template<class T, class U, class S> pair<T, U> operator+=(pair<T, U>& p, S n) { p.fi += n; p.se += n; return p; }template<class T, class U, class S> pair<T, U> operator*(pair<T, U> p, S n) { p.fi *= n; p.se *= n; return p; }template<class T, class U, class S> pair<T, U> operator*=(pair<T, U>& p, S n) { p.fi *= n; p.se *= n; return p; }template<class T, class U, class S> pair<T, U> operator/(pair<T, U> p, S n) { p.fi /= n; p.se /= n; return p; }template<class T, class U, class S> pair<T, U> operator/=(pair<T, U>& p, S n) { p.fi /= n; p.se /= n; return p; }template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "{" << p.first << "," << p.second << "}" << endl; return os;}template<class T, class U> istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }#if __has_include(<atcoder/all>)#include<atcoder/all>using namespace atcoder;ostream& operator<<(ostream& os, modint m) { os << m.val(); return os; }#endiftemplate<class T> istream& operator>>(istream& is, vector<T>& v) { for (int i = 0; i < v.size(); i++) is >> v[i]; return is; }template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < v.size(); i++) { if (i) os << " "; os << v[i]; } os <<endl; return os; }template<class T, class G> ostream& operator<<(ostream& os, const map<T, G>& m) { for (const auto& [x, y] : m) os << "{" << x << "," << y << "}" <<endl; return os; }template<class T> ostream& operator<<(ostream& os, const set<T>& s) { for (const auto& x : s) os << x << " "; os << endl; return os; }template<class T, class U, class F, class G> pair<T, U> operator+(pair<T, U> p, pair<F, G> q) { p.first += q.first; p.second += q.second; return p; }template<class T, class U, class F, class G> pair<T, U> operator-(pair<T, U> p, pair<F, G> q) { p.first -= q.first; p.second -= q.second; return p; }string operator*(const string& s, int n) { string ret = ""; for (int i = 0; i < n; i++) ret += s; return ret; }string operator*=(string& s, int n) { s = s * n; return s; }template<class T> void print(T s) { cout << s << endl; }template<class T> void print(vc<T>& v) { for (int i = 0; i < v.size(); i++)cout << v[i] << " "; cout << endl; }template<class T> void print(vvc<T>& v) { For(x, v)print(x); return; }template<class... T>void print(T&... a) { (cout << ... << a); return; }template<class... T>void read(T&... a) { (cin >> ... >> a); }template<class T>T read() { T s; cin >> s; return s; }vi viread(int n) { vi a(n); cin >> a; return a; }vl vlread(int n) { vl a(n); cin >> a; return a; }vs vsread(int n) { vs a(n); cin >> n; return a; }int iread() { int s = read<int>(); return s; }ll lread() { ll s = read<ll>(); return s; }string sread() { string s = read<string>(); return s; }char cread() { char s = read<char>(); return s; }template<class T> T min(const vector<T>& v) { return *min_element(all(v)); }template<class T> T max(const vector<T>& v) { return *max_element(all(v)); }template<class T> vector<T> vread(int n) { vector<T>v(n); rep(i, n)read(v[i]); return v; }vvi readgraph(int n, int m) { vvi road(n); rep(i, m) { int a, b; cin >> a >> b; a--; b--; road[a].pb(b); road[b].pb(a); } return road; }vvi readtree(int n) { return readgraph(n, n - 1); }template<class T>vector<T> presum(vector<T>& v) { vector<T> s(v.size() + 1); rep(i, v.size())s[i + 1] = s[i] + v[i]; return s; }#define INT(...) int __VA_ARGS__; read(__VA_ARGS__)#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__)#define CH(...) char __VA_ARGS__; read(__VA_ARGS__)#define STR(...) string __VA_ARGS__; read(__VA_ARGS__)#define VC(a,b,c) vector<a> b(c);read(b);#define VVC(a,b,c,d)vvc<a>b(c,vc<a>(d));read(b);template<class T>vector<T> zaatu(vector<T>& v) {auto f = v;sort(all(f));f.erase(unique(all(f)), f.end());for (auto& x : v) {x = lower_bound(all(f), x) - f.begin();}return v;}template<class T>vector<vector<T>> rotate(vector<vector<T>>& v) {vector<vector<T>>ret(v[0].size(), vector<T>(v.size()));for (int i = 0; i < v[0].size(); i++)for (int j = 0; j < v.size(); j++) {ret[i][j] = v[j][i];}return ret;}//return their min and maxtemplate<class T, class S>pair<T, S> mmp(T s, S t) {return make_pair(min(s, t), max(s, t));}//O(NlogN) return if they are all different from otherstemplate<class T>bool all_unique(vector<T>& v) {set<T>s;for (auto x : v)s.is(x);return s.size() == v.size();}//return if they are all sametemplate<class T>bool all_same(std::vector<T>& v) {for (int i = 0; i + 1 < v.size(); i++) {if (v[i] != v[i + 1])return false;}return true;}std::vector<int>emp;//return if it is bipartite graph .if you give it x it wil also return an example to paint itbool is_two(vvi& road, vi& x = emp) {if (x == emp)x.resize(road.size(), -1);rep(i, road.size()) {if (x[i] == -1) {queue<int>que;que.push(i);x[i] = 0;while (que.size()) {auto p = que.front(); que.pop();for (auto y : road[p]) {if (x[y] == -1) {x[y] = 1 - x[p];que.push(y);}else {if (x[y] != 1 - x[p]) {return false;}}}}}}return true;}//return char and numbers of thatvector<std::pair<char, int>> run_length(const std::string& s) {std::pair<char, int>pre = { 'a',0 };std::vector<pair<char, int>>ret;for (auto x : s) {if (pre.first == x) {pre.second++;}else {if (pre.second)ret.push_back(pre);pre = { x,1 };}}ret.push_back(pre);return ret;}template < typename T > std::string to_string(const T& n) {std::ostringstream stm;stm << n;return stm.str();}template<class T> int cnts(std::vector<T>& v, T tmp, std::function<bool(T a, T b)>f) {int ret = 0;for (auto x : v) {if (f(x, tmp))ret++;}return ret;}//mathll Pow(ll a, ll b) { ll res = 1; rep(i, b) { res *= a; }return res; }ull POW(ull a, ull b) { ull res = 1; rep(i, b) { res *= a; }return res; }long long modpow(long long a, long long b, long long m) { if (a % m == 0)return 0; long long p = 1, q = a; q %= m; if (b < 0)return 0; for (int i = 0; i < 63; i++) { if ((b & (1LL << i)) != 0) { p *= q; p %= m; }q *= q; q %= m; }return p; }ll modinv(ll n, ll mod) { return modpow(n, mod - 2, mod); }ll gcd(ll a, ll b) { if (a == 0)return b; if (b == 0)return a; if (a % b == 0) { if (b > 0)return b; else return -b; } else { return gcd(b, a % b); }}ll lcm(ll a, ll b) { return a * b / gcd(a, b); }#pragma endregion//https://atcoder.jp/contests/abc312/submissions/48490412int n;vvi road;long long ans = 0;int dfs(int now,int par) {int s = 1;for (auto x : road[now]) {if (x == par)continue;int t=dfs(x,now);s +=t;ans += (ll)t *(n - t+1);ans+=(ll)(t+1)*(n-t);}return s;}void dfs2(int now, int par) {}void solve() {cin >> n;ans = n ;road= readtree(n);dfs(0, -1);cout << ans << endl;}signed main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(20);int t = 1;rep(i, t)solve();return 0;}