結果

問題 No.1418 Sum of Sum of Subtree Size
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 2023-06-19 20:04:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 4,001 bytes
コンパイル時間 2,304 ms
コンパイル使用メモリ 204,196 KB
最終ジャッジ日時 2025-02-14 23:01:53
ジャッジサーバーID
(参考情報)
judge6 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename S> struct Tree{
vector<vector<S>> E, par0;
vector<S> dist0;
S N, log=0;
Tree (const vector<vector<S>> &_E){
N = _E.size(); E = _E;
}
//from
vector<S> depth (S from) {
vector<S> dist(N);
_depth(from, -1, dist);
return dist;
}
void _depth(S from, S p, vector<S> &dist) {
for (auto to : E[from]){
if (to == p) continue;
dist[to] = dist[from]+1;
_depth(to, from, dist);
}
}
//(a, b)
S dist(S a, S b){
S c = lca(a, b);
return dist0[a] + dist0[b]- 2*dist0[c];
}
//(a, b)LCA
S lca(S a, S b){
if (par0.size() == 0){
dist0 = depth(0);
_doubling();
}
if (dist0[a] < dist0[b]) swap(a, b);
for (S i=0; i<=log; i++){
if ((dist0[a]-dist0[b]) & (1LL<<i)) a = par0[i][a];
}
if (a == b) return a;
for (S i=log; i>=0; i--){
if (par0[i][a] != par0[i][b]){
a = par0[i][a];
b = par0[i][b];
}
}
return par0[0][a];
}
void _doubling(){
S cnt = 1;
while(cnt < N){
cnt *= 2;
log++;
}
par0.resize(log+1, vector<S>(N));
_ancestor(0, -1);
for (S i=1; i<=log; i++){
for (S j=0; j<N; j++){
if (par0[i-1][j] == -1) par0[i][j] = -1;
else par0[i][j] = par0[i-1][par0[i-1][j]];
}
}
}
void _ancestor(S from, S p){
par0[0][from] = p;
for (auto to : E[from]){
if (to == p) continue;
_ancestor(to, from);
}
}
//fromgoal
vector<S> shortest_path(S from, S goal) const{
vector<S> path, pt;
_shortest_path(from, goal, -1, pt, path);
return path;
}
void _shortest_path(S from, S goal, S p, vector<S> &pt, vector<S> &path) const{
pt.push_back(from);
if (from == goal) path = pt;
for (auto to : E[from]){
if (to == p) continue;
_shortest_path(to, goal, from, pt, path);
}
pt.pop_back();
}
//
tuple<S, S, S> diameter() const{
S s=0, t=0, mx=0;
_diameter(s, -1, 0, mx, t);
s=t; t=0; mx=0;
_diameter(s, -1, 0, mx, t);
return make_tuple(s, t, mx);
}
void _diameter(S from, S p, S d, S &mx, S &argmx) const{
if (d > mx){
argmx = from; mx = d;
}
for (auto to : E[from]){
if (to == p) continue;
_diameter(to, from, d+1, mx, argmx);
}
}
//from
vector<S> subtree_size(S from) const{
vector<S> subtree(N);
_subtree_size(from, -1, subtree);
return subtree;
}
S _subtree_size(S from, S p, vector<S> &subtree) const{
S cnt = 1;
for (auto to : E[from]){
if (to == p) continue;
cnt += _subtree_size(to, from, subtree);
}
return subtree[from] = cnt;
}
};
int main(){
long long N, A, B, m, ans=0;
cin >> N;
vector<vector<long long>> E(N);
ans = N*N;
for (int i=0; i < N-1; i++){
cin >> A >> B;
A--; B--;
E[A].push_back(B);
E[B].push_back(A);
}
Tree tree(E);
vector<ll> subtree = tree.subtree_size(0);
for (int i=0; i<N; i++){
for (auto x : E[i]){
m = subtree[x];
if (m > subtree[i]) m = N-subtree[i];
ans += m * (N-m);
}
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0