結果

問題 No.1418 Sum of Sum of Subtree Size
ユーザー t9unkubjt9unkubj
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
#endif
using 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; }
#endif
template<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 max
template<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 others
template<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 same
template<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 it 
bool 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 that 
vector<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;
}
//math
ll 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/48490412
int 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;
}
0