結果
| 問題 |
No.3193 Submit Your Solution
|
| ユーザー |
👑  potato167
|
| 提出日時 | 2025-06-27 22:50:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 22,447 bytes |
| コンパイル時間 | 3,217 ms |
| コンパイル使用メモリ | 232,960 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-27 22:51:21 |
| 合計ジャッジ時間 | 14,885 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | TLE * 1 -- * 16 |
コンパイルメッセージ
e.cpp:75:43: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ e.cpp:87:40: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
ソースコード
//#include <bits/stdc++.h>
//using namespace std;
//using ll=unsigned long long;
//const ll ILL=2167167167167167167;
//const int INF=2100000000;
//#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
//#define all(p) p.begin(),p.end()
//template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
//template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
//template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
//template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
//template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
//template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
//template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
//bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
//template<class T> void vec_out(vector<T> &p,int ty=0){
// if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
// else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
//template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
//template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
//template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
//int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
//template<class T> T square(T a){return a * a;}
//
//template<class G> struct HLD {
// using vi = vector<int>;
//#define sz(p) (int)(p).size()
// G& g;
// ll n, id;
// vi siz, dep, down, up, nxt, par;
// void dfs_sz(ll i) {
// siz[i] = 1;
// if(sz(g[i]) > 1 && par[i] == g[i][0]) swap(g[i][0], g[i][1]);
// for(auto& j : g[i]) {
// if(j != par[i]) {
// dep[j] = dep[i] + 1;
// par[j] = i;
// dfs_sz(j);
// siz[i] += siz[j];
// if(siz[j] > siz[g[i][0]]) swap(j, g[i][0]);
// }
// }
// }
// void dfs_hld(ll i) {
// down[i] = id++;
// for(auto j : g[i]) if(j != par[i]) {
// nxt[j] = j == g[i][0] ? nxt[i] : j;
// dfs_hld(j);
// }
// up[i] = id;
// }
// // [u, v)
// vector<pair<ll, ll>> ascend(ll u, ll v) {
// vector<pair<ll, ll>> res;
// while(nxt[u] != nxt[v]) {
// res.emplace_back(down[u], down[nxt[u]]);
// u = par[nxt[u]];
// }
// if(u != v) res.emplace_back(down[u], down[v] + 1);
// return res;
// }
// // (u, v]
// vector<pair<ll, ll>> descend(ll u, ll v) {
// if(u == v) return {};
// if(nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
// auto res = descend(u, par[nxt[v]]);
// res.emplace_back(down[nxt[v]], down[v]);
// return res;
// }
// HLD(G& g, ll v = 0) : g(g), n(sz(g)), id(0), siz(n), dep(n), down(n, -1), up(n, -1), nxt(n, v), par(n, v) {
// dfs_sz(v);
// dfs_hld(v);
// }
// pair<ll, ll> idx(ll i) { return {down[i], up[i]}; }
// void path_query(ll u, ll v, bool vtx, auto f, bool commut = 0) {
// ll l = lca(u, v);
// for(auto [s, t] : ascend(u, l)) {
// s++;
// (!commut && s > t) ? f(t, s) : f(s, t);
// }
// if(vtx) f(down[l], down[l] + 1);
// for(auto [s, t] : descend(l, v)) {
// t++;
// (!commut && s > t) ? f(t, s) : f(s, t);
// }
// }
// void subtree_query(ll u, bool vtx, auto f) {
// f(down[u] + !vtx, up[u]);
// }
// ll lca(ll a, ll b) {
// while(nxt[a] != nxt[b]) {
// if(down[a] < down[b]) swap(a, b);
// a = par[nxt[a]];
// }
// return dep[a] < dep[b] ? a : b;
// }
// ll dist(ll a, ll b) { return dep[a] + dep[b] - dep[lca(a, b)] * 2; }
//};
//
//#include <atcoder/lazysegtree>
//
//struct lazy_S {
// ll sum = 0;
// ll cou = 0;
//};
//
//using lazy_F = ll;
//
//lazy_S lazy_op(lazy_S l, lazy_S r) {
// return lazy_S{
// l.sum + r.sum, l.cou + r.cou
// };
//}
//
//lazy_S lazy_e() { return lazy_S{}; }
//
//lazy_S mapping(lazy_F l, lazy_S r) {
// r.sum += r.cou * l;
// return r;
//}
//
////l(r(x))
//lazy_F composition(lazy_F l, lazy_F r) {
// return l + r;
//}
//
//lazy_F lazy_id(){return 0;}
//
//#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id
//
//#include "po167_library/graph/tree/LCA.hpp"
//
//
//std::vector<std::vector<int>> tree_in(int N){
// std::vector<std::vector<int>> G(N);
// for(int i=0;i<N-1;i++){
// int a;int b;
// cin>>a>>b;
// a--,b--;
// G[a].push_back(b);
// G[b].push_back(a);
// }
// return G;
//}
//std::tuple<std::vector<int>,std::vector<int>,std::vector<int>> tree_order_pare_depth(std::vector<std::vector<int>> &G,int root=0){
// int n=G.size();
// std::vector<int> order={root},pare(n,-1),depth(n);
// pare[root]=-2;
// for(int i=0;i<n;i++){
// int a=order[i];
// for(auto x:G[a]){
// if(pare[x]==-1){
// pare[x]=a;
// depth[x]=depth[a]+1;
// order.push_back(x);
// }
// }
// }
// return {order,pare,depth};
//}
//std::vector<int> tree_diameter_path(std::vector<std::vector<int>> &G){
// int n=G.size();
// auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1);
// std::vector<int> order,pare,depth,ans;
// tie(order,pare,depth)=tree_order_pare_depth(G,r);
// int ind=order[n-1];
// while(ind!=-2){
// ans.push_back(ind);
// ind=pare[ind];
// }
// return ans;
//}
//
//void solve();
//// POP'N ROLL MUSIC / TOMOO
//int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int t = 1;
// // cin >> t;
// rep(i, 0, t) solve();
//}
//
//void solve(){
// int N;
// cin >> N;
// auto G = tree_in(N);
// auto H = tree_in(N);
// vector<ll> dist_sum(N);
// vector<int> D;
// vector<ll> H_wei(N, 1);
// {
// auto [order, pare, depth] = tree_order_pare_depth(H);
// D = depth;
// dist_sum[0] = vec_sum(depth);
// reverse(all(order));
// rep(i, 0, N - 1){
// int a = order[i];
// H_wei[pare[a]] += H_wei[a];
// }
// reverse(all(order));
// rep(i, 1, N){
// int a = order[i];
// dist_sum[a] = dist_sum[pare[a]] + N - 2 * H_wei[a];
// }
// }
// ll ans = 0;
// ll now_var_dist_sum = dist_sum[0];
// ll now_var = 0;
// ll now_pair_sum = 0;
// ll zentai = N;
// vector<ll> edge(N, 1);
// /*
// * ペアサムの更新
// * +- 切り替えるペアの +- の和が分かれば、
// * + -> - なら、(dist_sum[var] + [+- の和]) / 2 をペアサムにたす
// * じゃあ、+- をどうやって求めるかというと、
// * 頂点 0 における +1 和がわかっているとき、
// * 頂点 0 から v への辺の重みの和とすればいい。
// * 辺の重みは、-2 * (辺の下にある +- の和) + 全体の +- の和
// * 全体の +- 和は持っておけばいい
// */
// vector<lazy_S> base(N);
// HLD hld(H);
// rep(i, 0, N) base[hld.down[i]] = {H_wei[i], 1};
// atcoder::lazy_segtree<lazy_calc> seg(base);
//
// auto upd_seg = [&](int l, int r){
// seg.apply(l, r, 2 * edge[now_var]);
// };
// ll tmp;
// auto sum_seg = [&](int l, int r){
// tmp -= 2 * seg.prod(l, r).sum;
// tmp += zentai * (r - l);
// };
// auto my_set = [&](int var){
// now_var = var;
// // var 0 の答えを更新する
// now_var_dist_sum -= edge[var] * D[var] * 2;
// // zentai の更新
// zentai -= edge[var] * 2;
// // edge の更新
// edge[var] *= -1;
// // seg の更新
// hld.path_query(0, var, 0, upd_seg);
// // 答えの更新
// tmp = now_var_dist_sum;
// hld.path_query(0, var, 0, sum_seg);
// now_pair_sum -= tmp * edge[var];
// // cout << var << " " << now_pair_sum << " " << tmp<< "\n";
// // vec_out(edge);
// };
// vector<int> wei(N);
// {
// auto [order, pare, depth] = tree_order_pare_depth(G);
// reverse(all(order));
// rep(i, 0, N - 1){
// int a = order[i];
// wei[pare[a]] += wei[a];
// }
// }
// auto dfs_my_set = [&](auto self, int var, int pare) -> void {
// my_set(var);
// for (auto x : G[var]){
// if (x != pare) self(self, x, var);
// }
// };
// auto f = [&](auto self, int var, int pare) -> void {
// // cout << var << " " << now_pair_sum << "\n";
// ans += now_pair_sum;
// vector<int> ch;
// for (auto x : G[var]){
// if (x != pare) ch.push_back(x);
// }
// if (ch.empty()){
// my_set(var);
// return;
// }
// sort(all(ch), [&](int l, int r){
// return wei[l] > wei[r];
// });
// my_set(var);
// rep(i, 1, ch.size()){
// dfs_my_set(dfs_my_set, ch[i], var);
// }
// self(self, ch[0], var);
// rep(i, 1, ch.size()){
// dfs_my_set(dfs_my_set, ch[i], var);
// self(self, ch[i], var);
// }
// };
// f(f, 0, -1);
// ans *= 2;
// cout << ans << "\n";
//}
#line 1 "e.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}
template<class G> struct HLD {
using vi = vector<int>;
#define sz(p) (int)(p).size()
G& g;
ll n, id;
vi siz, dep, down, up, nxt, par;
void dfs_sz(ll i) {
siz[i] = 1;
if(sz(g[i]) > 1 && par[i] == g[i][0]) swap(g[i][0], g[i][1]);
for(auto& j : g[i]) {
if(j != par[i]) {
dep[j] = dep[i] + 1;
par[j] = i;
dfs_sz(j);
siz[i] += siz[j];
if(siz[j] > siz[g[i][0]]) swap(j, g[i][0]);
}
}
}
void dfs_hld(ll i) {
down[i] = id++;
for(auto j : g[i]) if(j != par[i]) {
nxt[j] = j == g[i][0] ? nxt[i] : j;
dfs_hld(j);
}
up[i] = id;
}
// [u, v)
vector<pair<ll, ll>> ascend(ll u, ll v) {
vector<pair<ll, ll>> res;
while(nxt[u] != nxt[v]) {
res.emplace_back(down[u], down[nxt[u]]);
u = par[nxt[u]];
}
if(u != v) res.emplace_back(down[u], down[v] + 1);
return res;
}
// (u, v]
vector<pair<ll, ll>> descend(ll u, ll v) {
if(u == v) return {};
if(nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
auto res = descend(u, par[nxt[v]]);
res.emplace_back(down[nxt[v]], down[v]);
return res;
}
HLD(G& g, ll v = 0) : g(g), n(sz(g)), id(0), siz(n), dep(n), down(n, -1), up(n, -1), nxt(n, v), par(n, v) {
dfs_sz(v);
dfs_hld(v);
}
pair<ll, ll> idx(ll i) { return {down[i], up[i]}; }
void path_query(ll u, ll v, bool vtx, auto f, bool commut = 0) {
ll l = lca(u, v);
for(auto [s, t] : ascend(u, l)) {
s++;
(!commut && s > t) ? f(t, s) : f(s, t);
}
if(vtx) f(down[l], down[l] + 1);
for(auto [s, t] : descend(l, v)) {
t++;
(!commut && s > t) ? f(t, s) : f(s, t);
}
}
void subtree_query(ll u, bool vtx, auto f) {
f(down[u] + !vtx, up[u]);
}
ll lca(ll a, ll b) {
while(nxt[a] != nxt[b]) {
if(down[a] < down[b]) swap(a, b);
a = par[nxt[a]];
}
return dep[a] < dep[b] ? a : b;
}
ll dist(ll a, ll b) { return dep[a] + dep[b] - dep[lca(a, b)] * 2; }
};
#include <atcoder/lazysegtree>
struct lazy_S {
ll sum = 0;
ll cou = 0;
};
using lazy_F = ll;
lazy_S lazy_op(lazy_S l, lazy_S r) {
return lazy_S{
l.sum + r.sum, l.cou + r.cou
};
}
lazy_S lazy_e() { return lazy_S{}; }
lazy_S mapping(lazy_F l, lazy_S r) {
r.sum += r.cou * l;
return r;
}
//l(r(x))
lazy_F composition(lazy_F l, lazy_F r) {
return l + r;
}
lazy_F lazy_id(){return 0;}
#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id
#line 4 "/Users/Shared/po167_library/ds/Sparse_table.hpp"
namespace po167{
template<class T, T(*op)(T, T)>
struct Sparse_table{
int n;
int depth;
std::vector<std::vector<T>> val;
void init(std::vector<T> &v){
depth = 1;
n = v.size();
while ((1 << depth) <= n) depth++;
val.resize(depth);
val[0] = v;
for (int i = 1; i < depth; i++){
val[i].resize(n);
for (int j = 0; j <= n - (1 << i); j++){
val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
}
}
}
Sparse_table(std::vector<T> v){
init(v);
}
Sparse_table(){}
// 0 <= l < r <= n
// if l == r : assert
T prod(int l, int r){
assert(0 <= l && l < r && r <= n);
int z=31-__builtin_clz(r-l);
return op(val[z][l], val[z][r - (1 << z)]);
}
};
}
#line 6 "/Users/Shared/po167_library/graph/tree/LCA.hpp"
namespace po167{
int op(int a, int b){
return std::min(a, b);
}
struct LCA{
Sparse_table<int, op> table;
std::vector<int> depth;
std::vector<int> E;
std::vector<int> order;
int var_num;
void init(std::vector<std::vector<int>> &g, int root = 0){
var_num = g.size();
assert(0 <= root && root < var_num);
std::vector<int> val;
depth.assign(var_num, -1);
depth[root] = 0;
E.resize(var_num);
std::vector<int> tmp;
order.clear();
tmp.reserve(var_num);
order.reserve(var_num);
int c = 0;
auto dfs = [&](auto self, int var, int pare) -> void {
E[var] = c++;
if (var != root) tmp.push_back(E[pare]);
order.push_back(var);
for (auto x : g[var]) if (depth[x] == -1){
depth[x] = depth[var] + 1;
self(self, x, var);
}
};
dfs(dfs, root, -1);
assert(c == var_num);
table.init(tmp);
}
void init(std::vector<int> &pare){
int root = -1;
int n = pare.size();
std::vector<std::vector<int>> g(n);
for (int i = 0; i < n; i++){
if (pare[i] < 0){
assert(root == -1);
root = i;
}
else{
assert(0 <= pare[i] && pare[i] < n);
g[pare[i]].push_back(i);
}
}
assert(root != -1);
init(g, root);
}
LCA (std::vector<std::vector<int>> g, int root = 0){
init(g, root);
}
LCA (std::vector<int> pare){
init(pare);
}
LCA(){
}
int lca(int a, int b){
assert(0 <= std::min(a, b) && std::max(a, b) < var_num);
if (a == b) return a;
if (E[a] > E[b]) std::swap(a, b);
return order[table.prod(E[a], E[b])];
}
int dist(int a, int b){
assert(0 <= std::min(a, b) && std::max(a, b) < var_num);
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
int back(int var, int len){
assert(len <= depth[var]);
if (len == 0) return var;
int l = 0, r = E[var];
while (r - l > 1){
int m = (l + r) / 2;
if (depth[var] - depth[order[table.prod(m, E[var])]] < len){
r = m;
}
else l = m;
}
return order[table.prod(l, E[var])];
}
// a -> b
int jump(int a, int b, int len){
int c = lca(a, b);
if (len <= depth[a] - depth[c]) return back(a, len);
len -= depth[a] - depth[c];
if (len <= depth[b] - depth[c]) return back(b, depth[b] - depth[c] - len);
return -1;
}
};
}
#line 132 "e.cpp"
std::vector<std::vector<int>> tree_in(int N){
std::vector<std::vector<int>> G(N);
for(int i=0;i<N-1;i++){
int a;int b;
cin>>a>>b;
a--,b--;
G[a].push_back(b);
G[b].push_back(a);
}
return G;
}
std::tuple<std::vector<int>,std::vector<int>,std::vector<int>> tree_order_pare_depth(std::vector<std::vector<int>> &G,int root=0){
int n=G.size();
std::vector<int> order={root},pare(n,-1),depth(n);
pare[root]=-2;
for(int i=0;i<n;i++){
int a=order[i];
for(auto x:G[a]){
if(pare[x]==-1){
pare[x]=a;
depth[x]=depth[a]+1;
order.push_back(x);
}
}
}
return {order,pare,depth};
}
std::vector<int> tree_diameter_path(std::vector<std::vector<int>> &G){
int n=G.size();
auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1);
std::vector<int> order,pare,depth,ans;
tie(order,pare,depth)=tree_order_pare_depth(G,r);
int ind=order[n-1];
while(ind!=-2){
ans.push_back(ind);
ind=pare[ind];
}
return ans;
}
void solve();
// POP'N ROLL MUSIC / TOMOO
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
rep(i, 0, t) solve();
}
void solve(){
int N;
cin >> N;
auto G = tree_in(N);
auto H = tree_in(N);
vector<ll> dist_sum(N);
vector<int> D;
vector<ll> H_wei(N, 1);
{
auto [order, pare, depth] = tree_order_pare_depth(H);
D = depth;
dist_sum[0] = vec_sum(depth);
reverse(all(order));
rep(i, 0, N - 1){
int a = order[i];
H_wei[pare[a]] += H_wei[a];
}
reverse(all(order));
rep(i, 1, N){
int a = order[i];
dist_sum[a] = dist_sum[pare[a]] + N - 2 * H_wei[a];
}
}
ll ans = 0;
ll now_var_dist_sum = dist_sum[0];
ll now_var = 0;
ll now_pair_sum = 0;
ll zentai = N;
vector<ll> edge(N, 1);
/*
* ペアサムの更新
* +- 切り替えるペアの +- の和が分かれば、
* + -> - なら、(dist_sum[var] + [+- の和]) / 2 をペアサムにたす
* じゃあ、+- をどうやって求めるかというと、
* 頂点 0 における +1 和がわかっているとき、
* 頂点 0 から v への辺の重みの和とすればいい。
* 辺の重みは、-2 * (辺の下にある +- の和) + 全体の +- の和
* 全体の +- 和は持っておけばいい
*/
vector<lazy_S> base(N);
HLD hld(H);
rep(i, 0, N) base[hld.down[i]] = {H_wei[i], 1};
atcoder::lazy_segtree<lazy_calc> seg(base);
auto upd_seg = [&](int l, int r){
seg.apply(l, r, 2 * edge[now_var]);
};
ll tmp;
auto sum_seg = [&](int l, int r){
tmp -= 2 * seg.prod(l, r).sum;
tmp += zentai * (r - l);
};
auto my_set = [&](int var){
now_var = var;
// var 0 の答えを更新する
now_var_dist_sum -= edge[var] * D[var] * 2;
// zentai の更新
zentai -= edge[var] * 2;
// edge の更新
edge[var] *= -1;
// seg の更新
hld.path_query(0, var, 0, upd_seg);
// 答えの更新
tmp = now_var_dist_sum;
hld.path_query(0, var, 0, sum_seg);
now_pair_sum -= tmp * edge[var];
// cout << var << " " << now_pair_sum << " " << tmp<< "\n";
// vec_out(edge);
};
vector<int> wei(N);
{
auto [order, pare, depth] = tree_order_pare_depth(G);
reverse(all(order));
rep(i, 0, N - 1){
int a = order[i];
wei[pare[a]] += wei[a];
}
}
auto dfs_my_set = [&](auto self, int var, int pare) -> void {
my_set(var);
for (auto x : G[var]){
if (x != pare) self(self, x, var);
}
};
auto f = [&](auto self, int var, int pare) -> void {
// cout << var << " " << now_pair_sum << "\n";
ans += now_pair_sum;
vector<int> ch;
for (auto x : G[var]){
if (x != pare) ch.push_back(x);
}
if (ch.empty()){
my_set(var);
return;
}
sort(all(ch), [&](int l, int r){
return wei[l] > wei[r];
});
my_set(var);
rep(i, 1, ch.size()){
dfs_my_set(dfs_my_set, ch[i], var);
}
self(self, ch[0], var);
rep(i, 1, ch.size()){
dfs_my_set(dfs_my_set, ch[i], var);
self(self, ch[i], var);
}
};
f(f, 0, -1);
ans *= 2;
cout << ans << "\n";
}