結果
| 問題 |
No.3193 Submit Your Solution
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-06-27 23:33:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6,654 ms / 10,000 ms |
| コード長 | 20,987 bytes |
| コンパイル時間 | 5,446 ms |
| コンパイル使用メモリ | 333,536 KB |
| 実行使用メモリ | 129,152 KB |
| 最終ジャッジ日時 | 2025-06-27 23:35:34 |
| 合計ジャッジ時間 | 83,654 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=200005,INF=15<<26;
// https://judge.yosupo.jp/submission/294286
#line 1 "c.cpp"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#line 2 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
using namespace std;
#include<bits/stdc++.h>
#line 1 "/Users/noya2/Desktop/Noya2_library/template/inout_old.hpp"
namespace noya2 {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p){
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v){
for (auto &x : v) is >> x;
return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u){
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u){
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
template<typename T>
void out(const vector<vector<T>> &vv){
int s = (int)vv.size();
for (int i = 0; i < s; i++) out(vv[i]);
}
struct IoSetup {
IoSetup(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetup_noya2;
} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/const.hpp"
namespace noya2{
const int iinf = 1'000'000'007;
const long long linf = 2'000'000'000'000'000'000LL;
const long long mod998 = 998244353;
const long long mod107 = 1000000007;
const long double pi = 3.14159265358979323;
const vector<int> dx = {0,1,0,-1,1,1,-1,-1};
const vector<int> dy = {1,0,-1,0,1,-1,-1,1};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string NUM = "0123456789";
void yes(){ cout << "Yes\n"; }
void no(){ cout << "No\n"; }
void YES(){ cout << "YES\n"; }
void NO(){ cout << "NO\n"; }
void yn(bool t){ t ? yes() : no(); }
void YN(bool t){ t ? YES() : NO(); }
} // namespace noya2
#line 2 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
#line 6 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
namespace noya2{
unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
if (a == 0 || b == 0) return a + b;
int n = __builtin_ctzll(a); a >>= n;
int m = __builtin_ctzll(b); b >>= m;
while (a != b) {
int mm = __builtin_ctzll(a - b);
bool f = a > b;
unsigned long long c = f ? a : b;
b = f ? b : a;
a = (c - b) >> mm;
}
return a << std::min(n, m);
}
template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }
long long sqrt_fast(long long n) {
if (n <= 0) return 0;
long long x = sqrt(n);
while ((x + 1) * (x + 1) <= n) x++;
while (x * x > n) x--;
return x;
}
template<typename T> T floor_div(const T n, const T d) {
assert(d != 0);
return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}
template<typename T> T ceil_div(const T n, const T d) {
assert(d != 0);
return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}
template<typename T> void uniq(std::vector<T> &v){
std::sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }
} // namespace noya2
#line 8 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define repp(i,m,n) for (int i = (m); i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
namespace noya2{
/* ~ (. _________ . /) */
}
using namespace noya2;
#line 3 "c.cpp"
struct fast_lca {
int n;
std::vector<int> down;
std::vector<int> a, pre, suf;
std::vector<std::vector<int>> st;
static constexpr int LG = 4;
static constexpr int MASK = (1 << LG) - 1;
fast_lca (const std::vector<int> &par) : n(par.size()), down(n), a(n) {
//ncout<<n<<endl;
assert(n >= 1);
// subtree size - 1
for (int i = n - 1; i >= 1; i--){
down[par[i]] += down[i] + 1;
}
// euler tour time
for (int i = 1; i < n; i++){
down[i] = std::exchange(down[par[i]], down[par[i]] - down[i] - 1);
}
// build a, pre, suf
for (int i = 1; i < n; i++){
a[down[i] - 1] = par[i];
}
pre = suf = a;
for (int i = 1; i < n; i++){
if (i & MASK){
if (pre[i] > pre[i - 1]){
pre[i] = pre[i - 1];
}
}
}
for (int i = n - 1; i >= 1; i--){
if (i & MASK){
if (suf[i - 1] > suf[i]){
suf[i - 1] = suf[i];
}
}
}
// build st
int n2 = n >> LG;
int lg = (n2 <= 1 ? 1 : std::bit_width<uint32_t>(n2 - 1));
st.resize(lg);
st[0].resize(n2);
for (int i = 0; i < n2; i++){
st[0][i] = suf[i << LG];
}
for (int d = 0; d < lg - 1; d++){
int nsz = (int)(st[d].size()) - (1 << d);
st[d + 1].resize(nsz);
for (int i = 0; i < nsz; i++){
int x = st[d][i];
int y = st[d][i + (1 << d)];
st[d + 1][i] = (x < y ? x : y);
}
}
}
int st_prod(int l, int r){
if (l == r){
return std::numeric_limits<int>::max();
}
int k = std::bit_width<uint32_t>(r - l) - 1;
int x = st[k][l];
int y = st[k][r - (1 << k)];
return (x < y ? x : y);
}
int prod(int l, int r){
assert(l < r);
r--;
int x = l >> LG, y = r >> LG;
if (x < y){
int p1 = suf[l];
int p2 = st_prod(x + 1, y);
int p3 = pre[r];
return (p1 < p2 ? (p1 < p3 ? p1 : p3) : (p2 < p3 ? p2 : p3));
}
int ret = a[l];
for (int i = l + 1; i <= r; i++){
if (ret > a[i]){
ret = a[i];
}
}
return ret;
}
int lca(int u, int v){
if (u == v) return u;
u = down[u], v = down[v];
if (u > v) std::swap(u, v);
return prod(u, v);
}
};
#line 2 "fastio.hpp"
#line 4 "fastio.hpp"
namespace nachia{
struct CInStream{
private:
static const unsigned int INPUT_BUF_SIZE = 1 << 17;
unsigned int p = INPUT_BUF_SIZE;
static char Q[INPUT_BUF_SIZE];
public:
using MyType = CInStream;
char seekChar(){
if(p == INPUT_BUF_SIZE){
size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
if(len != INPUT_BUF_SIZE) Q[len] = '\0';
p = 0;
}
return Q[p];
}
void skipSpace(){ while(isspace(seekChar())) p++; }
private:
template<class T, int sp = 1>
T nextUInt(){
if constexpr (sp) skipSpace();
T buf = 0;
while(true){
char tmp = seekChar();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
public:
uint32_t nextU32(){ return nextUInt<uint32_t>(); }
int32_t nextI32(){
skipSpace();
if(seekChar() == '-'){
p++; return (int32_t)(-nextUInt<uint32_t, 0>());
}
return (int32_t)nextUInt<uint32_t, 0>();
}
uint64_t nextU64(){ return nextUInt<uint64_t>();}
int64_t nextI64(){
skipSpace();
if(seekChar() == '-'){
p++; return (int64_t)(-nextUInt<int64_t, 0>());
}
return (int64_t)nextUInt<int64_t, 0>();
}
template<class T>
T nextInt(){
skipSpace();
if(seekChar() == '-'){
p++;
return - nextUInt<T, 0>();
}
return nextUInt<T, 0>();
}
char nextChar(){ skipSpace(); char buf = seekChar(); p++; return buf; }
std::string nextToken(){
skipSpace();
std::string buf;
while(true){
char ch = seekChar();
if(isspace(ch) || ch == '\0') break;
buf.push_back(ch);
p++;
}
return buf;
}
MyType& operator>>(unsigned int& dest){ dest = nextU32(); return *this; }
MyType& operator>>(int& dest){ dest = nextI32(); return *this; }
MyType& operator>>(unsigned long& dest){ dest = nextU64(); return *this; }
MyType& operator>>(long& dest){ dest = nextI64(); return *this; }
MyType& operator>>(unsigned long long& dest){ dest = nextU64(); return *this; }
MyType& operator>>(long long& dest){ dest = nextI64(); return *this; }
MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
MyType& operator>>(char& dest){ dest = nextChar(); return *this; }
} ncin;
struct FastOutputTable{
char LZ[1000][4] = {};
char NLZ[1000][4] = {};
constexpr FastOutputTable(){
using u32 = uint_fast32_t;
for(u32 d=0; d<1000; d++){
LZ[d][0] = ('0' + d / 100 % 10);
LZ[d][1] = ('0' + d / 10 % 10);
LZ[d][2] = ('0' + d / 1 % 10);
LZ[d][3] = '\0';
}
for(u32 d=0; d<1000; d++){
u32 i = 0;
if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);
if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);
NLZ[d][i++] = '\0';
}
}
};
struct COutStream{
private:
using u32 = uint32_t;
using u64 = uint64_t;
using MyType = COutStream;
static const u32 OUTPUT_BUF_SIZE = 1 << 17;
static char Q[OUTPUT_BUF_SIZE];
static constexpr FastOutputTable TB = FastOutputTable();
u32 p = 0;
static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }
static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }
template<class T, class U> static void Fil(T& m, U& l, U x){ m = l/x; l -= m*x; }
public:
void next_dig9(u32 x){
u32 y;
Fil(y, x, P10(6));
nextCstr(TB.LZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
void nextChar(char c){
Q[p++] = c;
if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }
}
void nextEoln(){ nextChar('\n'); }
void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
void nextU32(uint32_t x){
u32 y = 0;
if(x >= P10(9)){
Fil(y, x, P10(9));
nextCstr(TB.NLZ[y]); next_dig9(x);
}
else if(x >= P10(6)){
Fil(y, x, P10(6));
nextCstr(TB.NLZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= P10(3)){
Fil(y, x, P10(3));
nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= 1) nextCstr(TB.NLZ[x]);
else nextChar('0');
}
void nextI32(int32_t x){
if(x >= 0) nextU32(x);
else{ nextChar('-'); nextU32((u32)-x); }
}
void nextU64(uint64_t x){
u32 y = 0;
if(x >= P10L(18)){
Fil(y, x, P10L(18));
nextU32(y);
Fil(y, x, P10L(9));
next_dig9(y); next_dig9(x);
}
else if(x >= P10L(9)){
Fil(y, x, P10L(9));
nextU32(y); next_dig9(x);
}
else nextU32(x);
}
void nextI64(int64_t x){
if(x >= 0) nextU64(x);
else{ nextChar('-'); nextU64((u64)-x); }
}
template<class T>
void nextInt(T x){
if(x < 0){ nextChar('-'); x = -x; }
if(!(0 < x)){ nextChar('0'); return; }
std::string buf;
while(0 < x){
buf.push_back('0' + (int)(x % 10));
x /= 10;
}
for(int i=(int)buf.size()-1; i>=0; i--){
nextChar(buf[i]);
}
}
void writeToFile(bool flush = false){
fwrite(Q, p, 1, stdout);
if(flush) fflush(stdout);
p = 0;
}
COutStream(){ Q[0] = 0; }
~COutStream(){ writeToFile(); }
MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }
MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }
MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }
MyType& operator<<(int tg){ nextI32(tg); return *this; }
MyType& operator<<(long tg){ nextI64(tg); return *this; }
MyType& operator<<(long long tg){ nextI64(tg); return *this; }
MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }
MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }
MyType& operator<<(char tg){ nextChar(tg); return *this; }
} ncout;
char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];
} // namespace nachia
#line 95 "c.cpp"
fast_lca fl({0});
int dep[MAX],parr[MAX];
vi G2[MAX];
void init(int u,int p){
for(int to:G2[u]){
if(to==p) continue;
dep[to]=dep[u]+1;
parr[to]=u;
init(to,u);
}
}
int lca(int a,int b){
return fl.lca(a,b);
}
int dd(int a,int b){
return dep[a]+dep[b]-dep[lca(a,b)]*2;
}
ll ans=0;
//auxiliary-tree
// https://beet-aizu.github.io/library/tree/auxiliarytree.cpp.html
struct LowestCommonAncestor{
int h;
vector< vector<int> > G,par;
vector<int> dep;
LowestCommonAncestor(int n):G(n),dep(n){
h=1;
while((1<<h)<=n) h++;
par.assign(h,vector<int>(n,-1));
}
void add_edge(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void dfs(int v,int p,int d){
par[0][v]=p;
dep[v]=d;
for(int u:G[v])
if(u!=p) dfs(u,v,d+1);
}
void build(int r=0){
int n=G.size();
dfs(r,-1,0);
for(int k=0;k+1<h;k++)
for(int v=0;v<n;v++)
if(~par[k][v])
par[k+1][v]=par[k][par[k][v]];
}
};
struct AuxiliaryTree : LowestCommonAncestor{
using super = LowestCommonAncestor;
vector<int> idx,iru;
vl cn,omo,dp;
vvll T;
AuxiliaryTree(int n):super(n),idx(n),iru(n),cn(n),omo(n),dp(n),T(n){}
void dfs(int v,int p,int &pos){
idx[v]=pos++;
for(int u:G[v])
if(u!=p) dfs(u,v,pos);
}
void build(int r=0){
super::build(r);
int pos=0;
dfs(r,-1,pos);
}
void add_aux_edge(int u,int v){
int d=dd(u,v);
T[u].emplace_back(mp(v,d));
T[v].emplace_back(mp(u,d));
}
using super::dep;
void query(vector<int> &vs){
assert(!vs.empty());
sort(vs.begin(),vs.end(),
[&](int a,int b){return idx[a]<idx[b];});
vs.erase(unique(vs.begin(),vs.end()),vs.end());
int k=vs.size();
stack<int> st;
st.emplace(vs[0]);
for(int i=0;i+1<k;i++){
int w=lca(vs[i],vs[i+1]);
if(w!=vs[i]){
int l=st.top();st.pop();
while(!st.empty() and dep[w]<dep[st.top()]){
add_aux_edge(st.top(),l);
l=st.top();st.pop();
}
if(st.empty() or st.top()!=w){
st.emplace(w);
vs.emplace_back(w);
}
add_aux_edge(w,l);
}
st.emplace(vs[i+1]);
}
while(st.size()>1){
int c=st.top();st.pop();
add_aux_edge(st.top(),c);
}
}
void make(int u,int p){
for(auto [to,dd]:T[u]){
if(to==p) continue;
make(to,u);
dp[u]+=dp[to];
dp[u]+=cn[to]*dd;
cn[u]+=cn[to];
}
}
void solve(int u,int p){
if(iru[u]) cn[u]=1;
else cn[u]=0;
dp[u]=0;
for(auto [to,dd]:T[u]){
dp[u]+=dp[to];
dp[u]+=cn[to]*dd;
cn[u]+=cn[to];
}
ans+=dp[u]*omo[u];
//cout<<u<<" "<<dp[u]<<" "<<cn[u]<<" "<<omo[u]<<endl;
for(auto [to,dd]:T[u]){
if(to==p) continue;
ll a=dp[u],b=cn[u],c=dp[to],d=cn[to];
dp[u]-=dp[to];
dp[u]-=cn[to]*dd;
cn[u]-=cn[to];
solve(to,u);
dp[u]=a;
cn[u]=b;
dp[to]=c;
cn[to]=d;
}
}
void clear(const vector<int> &ws){
for(int w:ws){
cn[w]=0;
omo[w]=0;
dp[w]=0;
iru[w]=0;
T[w].clear();
}
}
};
AuxiliaryTree AT(1);
//重心分解(使える版)
int N,C=-1;
vi G[MAX];
bool centroid[MAX];
int subtree_size[MAX];
int centpar[MAX];
int compute_subtree_size(int u,int p){
int c=1;
for(int a:G[u]){
if(a==p||centroid[a]) continue;
c+=compute_subtree_size(a,u);
}
return subtree_size[u]=c;
}
pair<int,int> search_centroid(int u,int p,int t){
pair<int,int> res={INF,-1};
int s=1,m=0;
for(int a:G[u]){
if(a==p||centroid[a]) continue;
res=min(res,search_centroid(a,u,t));
m=max(m,subtree_size[a]);
s+=subtree_size[a];
}
m=max(m,t-s);
res=min(res,{m,u});
return res;
}
void atume(int u,int p,int d,vii &T){
T.pb(mp(d,u));
for(int to:G[u]){
if(to==p||centroid[to]) continue;
atume(to,u,d+1,T);
}
}
void calc(vii S,int kei){
if(si(S)<=1) return;
vi use;
for(auto [a,b]:S) use.pb(b);
AT.query(use);
for(auto [a,b]:S){
AT.iru[b]=1;
AT.omo[b]=a*kei;
AT.cn[b]=1;
}
AT.make(use[0],-1);
AT.solve(use[0],-1);
AT.clear(use);
}
void solve_subproblem(int u,int p){
compute_subtree_size(u,-1);
int s=search_centroid(u,-1,subtree_size[u]).second;
centroid[s]=1;
if(C==-1) C=s;
centpar[s]=p;
vii S={mp(0,s)};
for(int a:G[s]){
if(centroid[a]){
continue;
}
vii T;
atume(a,s,1,T);
calc(T,-1);
for(auto x:T) S.pb(x);
solve_subproblem(a,s);
}
calc(S,1);
centroid[s]=0;
}
vi G3[MAX];
vi ss;
int jun[MAX];
void mkmk(int u,int p){
jun[u]=si(ss);
ss.pb(u);
for(int to:G3[u]){
if(to==p) continue;
mkmk(to,u);
}
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
using nachia::ncin, nachia::ncout;
ncin>>N;
vii E1,E2;
for(int i=0;i<N-1;i++){
int a,b;ncin>>a>>b;
a--;b--;
E1.pb(mp(a,b));
}
AT=AuxiliaryTree(N);
for(int i=0;i<N-1;i++){
int a,b;ncin>>a>>b;
a--;b--;
G3[a].pb(b);
G3[b].pb(a);
E2.pb(mp(a,b));
}
mkmk(0,-1);
for(auto [a,b]:E1){
a=jun[a];
b=jun[b];
G[a].pb(b);
G[b].pb(a);
}
for(auto [a,b]:E2){
a=jun[a];
b=jun[b];
G2[a].pb(b);
G2[b].pb(a);
AT.add_edge(a,b);
}
init(0,-1);
//ncout<<"A\n";
vi parw(N);
for(int i=0;i<N;i++){
parw[i]=parr[i];
}
//ncout<<N<<" "<<si(parw)<<"\n";
//return 0;
fl=fast_lca(parw);
//ncout<<"B\n";
AT.build();
solve_subproblem(0,-1);
ans*=2;
ncout<<ans<<"\n";
}