結果
| 問題 | No.3193 Submit Your Solution |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-06-28 17:08:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 5,695 ms / 10,000 ms |
| コード長 | 11,536 bytes |
| コンパイル時間 | 4,022 ms |
| コンパイル使用メモリ | 255,216 KB |
| 実行使用メモリ | 164,340 KB |
| 最終ジャッジ日時 | 2025-06-28 17:10:34 |
| 合計ジャッジ時間 | 72,740 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
template <typename T>
class SparseTable{
private:
T op(T a,T b){return min(a,b);} //条件op(A,A)=A &op(op(A,B),C)=op(A,op(B,C));
T e(T a,T b){return {1001001001,-1};}
array<int,400000> check;
array<array<T,400000>,19> table;
public:
void make(const vector<T> &A){
int n = A.size();
int p2 = 1,l = 0;
for(int i=1; i<400000; i++){
if(i == p2) check[i] = l,l++,p2 *= 2;
else check[i] = check[i-1];
}
for(int i=0; i<n; i++) table[0][i] = A[i];
for(int i=n; i<400000; i++) table[0][i] = {1001001001,-1};
l = 1;
for(int i=2; i<=n; i*=2,l++){
for(int k=0; k<=n-i; k++) table[l][k] = op(table[l-1][k],table[l-1][k+(i>>1)]);
for(int k=n-i+1; k<400000; k++) table[l][k] = {1001001001,-1};
}
}
T rangeans(int l,int r){//[L,R)だよ.
int pos = check[r-l]; r -= 1<<pos;
return op(table[pos][l],table[pos][r]);
}
};
int out[200000];
ull dist[200000];
class LCA{
private:
SparseTable<pair<int,int>> ST;
public:
array<int,200000> in;
void make3(const vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
int t = 0,dep = 0,n = Graph.size(),pos = root;
vector<pair<int,int>> depth;
vector<int> Itr(n,-1),P(n,-1);
while(pos != -1){
depth.push_back({dep,pos});
if(++Itr.at(pos) == 0) in[pos] = t;
int to = P.at(pos);
if(Itr.at(pos) == Graph.at(pos).size()) out[pos] = ++t;
else{
to = Graph.at(pos).at(Itr.at(pos));
if(to == P.at(pos)){
Itr.at(pos)++;
if(Itr.at(pos) == Graph.at(pos).size()) out[pos] = ++t;
else to = Graph.at(pos).at(Itr.at(pos));
}
}
if(to != P.at(pos)) dist[to] = dist[pos]+1,P.at(to) = pos,t++,dep++;
else dep--;
pos = to;
}
ST.make(depth);
}
int lca(int u,int v){
int tu = in[u],tv = in[v];
if(tu > tv) swap(tu,tv);
return ST.rangeans(tu,tv+1).second;
}
};
LCA L;
bool stop[200000];
int in[200000],start[200001],To[400000];
vector<pair<int,int>> in2;
pair<vector<vector<int>>,vector<vector<vector<int>>>> AuxiliaryTree(const vector<int> &A,int maxa){
//色ごとに木を構築するやつ O(NlogN) 定数悪い実装.
//return {色ごとの実際の頂点番号,色ごとのTree}
//重み付きだったら修正必須.
int N = A.size();
vector<vector<int>> ret1(maxa);
vector<vector<vector<int>>> ret2(maxa);
for(auto [t,i] : in2) if(A.at(i) != -1) ret1.at(A.at(i)).emplace_back(i);
for(int i=0; i<maxa; i++){
auto &as = ret1.at(i);
int n = as.size();
for(int i=0; i<n-1; i++){
int pos1 = as.at(i),pos2 = as.at(i+1);
int pos3 = L.lca(pos1,pos2);
assert(pos3 != -1);
as.emplace_back(pos3);
}
sort(as.begin(),as.end(),[&](auto a,auto b){return in[a]<in[b];});
as.erase(unique(as.begin(),as.end()),as.end());
int siz = as.size();
ret2.at(i).resize(siz);
stack<pair<int,int>> st;
for(int k=0; k<siz; k++){
int pos = as.at(k),out1 = out[pos];
while(st.size()){
auto[bk,out2] = st.top();
if(out1 < out2){
ret2.at(i).at(bk).emplace_back(k);
ret2.at(i).at(k).emplace_back(bk);
break;
}
else st.pop();
}
st.push({k,out1});
}
}
return{ret1,ret2};
}
tuple<ull,ull,ull,ull> V[200000];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
//if(N != 199910) return 0;
vector<vector<int>> Graph(N);
for(int i=0; i<N-1; i++){
int u = i,v = i+1;
cin >> u >> v,u--; v--;
Graph.at(u).emplace_back(v);
Graph.at(v).emplace_back(u);
}
{
int point = 0;
for(int i=0; i<N; i++){
start[i] = point;
for(auto to : Graph.at(i)) To[point++] = to;
Graph.at(i).clear();
}
start[N] = point;
}
for(int i=0; i<N-1; i++){
int u = i,v = i+1;
cin >> u >> v,u--; v--;
Graph.at(u).emplace_back(v);
Graph.at(v).emplace_back(u);
}
L.make3(Graph,0);
for(int i=0; i<N; i++) in[i] = L.in[i];
in2.resize(N);
for(int i=0; i<N; i++) in2.at(i) = {in[i],i};
sort(in2.begin(),in2.end());
ull answer = 0;
auto findsiz = [&](int s) -> int {
stack<tuple<int,int,int,int>> st;
st.push({1,s,start[s],-1});
int bring = 0;
while(st.size()){
auto &[vs,pos,i,back] = st.top();
vs += bring; bring = 0;
while(true){
if(i == start[pos+1]){bring = vs; st.pop(); break;}
int to = To[i]; i++;
if(stop[to] || to == back) continue;
st.push({1,to,start[to],pos}); break;
}
}
return bring;
};
auto centroid = [&](int s,int siz) -> int {
stack<tuple<int,int,int,int,bool>> st;
st.push({1,s,start[s],-1,true});
int bring = 0;
while(st.size()){
auto &[vs,pos,i,back,ok] = st.top();
if(bring > siz/2) ok = false;
vs += bring; bring = 0;
while(true){
if(i == start[pos+1]){
bring = vs;
if(siz-bring <= siz/2 && ok) return pos;
st.pop(); break;
}
int to = To[i]; i++;
if(stop[to] || to == back) continue;
st.push({1,to,start[to],pos,true}); break;
}
}
return -1;
};
vector<int> Ps = {0};
vector<double> T(10);
while(Ps.size()){
T.at(2) -= clock();
for(auto &p : Ps){
int siz = findsiz(p);
if(siz != 1) p = centroid(p,siz);
else stop[p] = true,p = -1;
}
T.at(2) += clock();
vector<int> C1(N,-1),C2(N,-1);
int cpos1 = 0,cpos2 = 0;
for(auto &p : Ps){
if(p == -1) continue;
auto dfs = [&](int s,int b) -> void {
stack<tuple<int,int,int>> st;
st.push({s,start[s],b});
C1.at(s) = cpos1,C2.at(s) = cpos2;
while(st.size()){
auto &[pos,i,back] = st.top();
while(true){
if(i == start[pos+1]){st.pop(); break;}
int to = To[i]; i++;
if(stop[to] || to == back) continue;
C1.at(to) = cpos1,C2.at(to) = cpos2;
st.push({to,start[to],pos}); break;
}
}
};
for(int i=start[p]; i<start[p+1]; i++){
int to = To[i];
if(stop[to] == false) dfs(to,p),cpos2++;
}
C1.at(p) = cpos1++;
}
T.at(0) -= clock();
auto[B1,G1] = AuxiliaryTree(C1,cpos1);
auto[B2,G2] = AuxiliaryTree(C2,cpos2);
T.at(0) += clock();
cpos1 = 0;
T.at(1) -= clock();
for(auto root : Ps) if(root != -1){
auto &G = G1.at(cpos1);
auto &B = B1.at(cpos1);
{
auto dfs = [&](int s) -> void {
stack<tuple<int,int,int>> st;
st.push({s,start[s],-1});
V[s] = {1,0,dist[s],0};
int dep = 0;
while(st.size()){
auto &[pos,i,back] = st.top();
while(true){
if(i == start[pos+1]){dep--,st.pop(); break;}
int to = To[i++];
if(stop[to] || to == back) continue;
dep++; V[to] = {1,dep,dist[to],dep*dist[to]};
st.push({to,start[to],pos}); break;
}
}
};
dfs(root);
}
{
auto dfs = [&](auto dfs,int pos,int back) -> tuple<ull,ull,ull,ull> {
int p = B.at(pos);
auto [c,d,e,s] = V[p]; V[p] = {0,0,0,0};
ull di = dist[p]*2;
for(auto to : G.at(pos)){
if(to == back) continue;
auto [c2,d2,e2,s2] = dfs(dfs,to,pos);
if(c2 == 0) continue;
answer -= di*d*c2;
answer -= di*d2*c;
answer += d*e2+e*d2;
answer += s*c2+s2*c;
c += c2,d += d2,e += e2,s += s2;
}
return {c,d,e,s};
};
dfs(dfs,0,-1);
}
cpos1++;
}
cpos2 = 0;
for(auto p : Ps) if(p != -1) for(int i=start[p]; i<start[p+1]; i++){
int root = To[i];
if(stop[root]) continue;
auto &G = G2.at(cpos2);
auto &B = B2.at(cpos2);
{
auto dfs = [&](int s,int b) -> void {
stack<tuple<int,int,int>> st;
st.push({s,start[s],b});
V[s] = {1,1,dist[s],dist[s]};
int dep = 1;
while(st.size()){
auto &[pos,i,back] = st.top();
while(true){
if(i == start[pos+1]){dep--,st.pop(); break;}
int to = To[i]; i++;
if(stop[to] || to == back) continue;
dep++; V[to] = {1,dep,dist[to],dep*dist[to]};
st.push({to,start[to],pos}); break;
}
}
};
dfs(root,p);
}
{
auto dfs = [&](auto dfs,int pos,int back) -> tuple<ull,ull,ull,ull> {
int p = B.at(pos);
auto [c,d,e,s] = V[p]; V[p] = {0,0,0,0};
ull di = dist[p]*2;
for(auto to : G.at(pos)){
if(to == back) continue;
auto [c2,d2,e2,s2] = dfs(dfs,to,pos);
answer += di*(d*c2+d2*c);
answer -= d*e2+e*d2;
answer -= s*c2+s2*c;
c += c2,d += d2,e += e2,s += s2;
}
return {c,d,e,s};
};
dfs(dfs,0,-1);
}
cpos2++;
}
T.at(1) += clock();
vector<int> next;
for(auto &p : Ps){
if(p == -1) continue;
for(int i=start[p]; i<start[p+1]; i++){
int to = To[i];
if(!stop[to]) next.emplace_back(to);
}
stop[p] = true;
}
swap(Ps,next);
}
answer *= 2;
//answer = 77714187941852070; //さいあく
cout << answer << endl;
//for(auto &t : T) cout << t/CLOCKS_PER_SEC << " "; cout << endl;
}