結果
| 問題 | No.399 動的な領主 |
| コンテスト | |
| ユーザー |
 sorachandu
|
| 提出日時 | 2026-06-04 01:30:31 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 259 ms / 2,000 ms |
| コード長 | 7,436 bytes |
| 記録 | |
| コンパイル時間 | 3,129 ms |
| コンパイル使用メモリ | 353,884 KB |
| 実行使用メモリ | 24,060 KB |
| 最終ジャッジ日時 | 2026-06-04 01:30:39 |
| 合計ジャッジ時間 | 7,158 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include<atcoder/lazysegtree>
/*//--------------------------------------------------------
木に対して重軽分解をする構造体
refer:
https://info.atcoder.jp/entry/algorithm_lectures/heavy_light_decomposition
https://nachiavivias.github.io/cp-library/cpp/tree/heavy-light-decomposition.html
*///--------------------------------------------------------
struct HeavyLightDecomposition{
private:
int N;
std::vector<int> par;
std::vector<int> dep;
std::vector<int> siz;
std::vector<int> vertex;
std::vector<int> id;
std::vector<int> head;
public:
// G is tree that represented by AdjacencyList
HeavyLightDecomposition(std::vector<std::vector<int>> G,int root=0){
N=std::ssize(G);
par.assign(N,-1);
dep.assign(N,-1);
siz.assign(N,0);
vertex.assign(N,-1);
id.assign(N,-1);
head.assign(N,-1);
{
// calculate subtree size, put the heave child first in G.
auto dfs=[&](auto &dfs, int v, int p=-1) -> void {
par[v]=p;
dep[v]=(p==-1 ? 0 : dep[p]+1);
siz[v]=1;
if(!G[v].empty() and G[v][0]==p) std::swap(G[v][0],G[v].back());
for(int &w:G[v]){
if(w==p) continue;
dfs(dfs,w,v);
siz[v]+=siz[w];
if(siz[w]>siz[G[v][0]]) std::swap(G[v][0],w);
}
};
dfs(dfs,root);
}
{
int idx=0;
auto dfs=[&](auto &dfs,int v,int p=-1) -> void {
id[v]=idx;
vertex[idx++]=v;
for(int &w:G[v]){
if(w==p) continue;
bool heavy=(w==G[v][0]);
head[w]=(heavy?head[v]:w);
dfs(dfs,w,v);
}
};
head[root]=root;
dfs(dfs,root);
}
}
int numVertices() const { return N; }
// 頂点vの深さ (dep)
int depth(int v) const { return dep[v]; }
// 頂点vがHLD配列上で何番目か (id)
int toSeq(int v) const { return id[v]; }
// HLD配列[seqidx]の頂点番号 (vertex)
int toVertex(int seqidx) const { return vertex[seqidx]; }
// 頂点vの親 (根なら-1)
int parent(int v) const { return par[v]; }
// 頂点vのheavyRoot (heavyPathに乗っていなければ自身の番号を返す)
int heavyR(int v) const { return head[v]; }
// 頂点vのheaveChild 存在しなければ-1
int heavyC(int v) const {
if(toSeq(v)==N-1) return -1;
int cand=toVertex(toSeq(v)+1);
if(same(v,cand)) return cand;
return -1;
}
// 頂点uと頂点vが同一のheavyPathに乗っているか
bool same(int u,int v) const { return head[u]==head[v]; }
// 頂点uと頂点vについてHLD配列上でu<vを成立させる (外部クエリ処理用)
void normalizePair(int &u,int &v){ if(id[u]>id[v]) swap(u,v); }
// 頂点vがheavyPath上で何番目の頂点か
int distToHR(int v) const { return id[v]-id[head[v]]; }
// 頂点vが含まれるheavyPathを配列で返す stopV=trueでvで止まる
// O(len(heavyPath))
std::vector<int> heavyPath(int v,bool stopV=false) const {
std::vector<int> path;
int idx=id[head[v]];
while(idx!=-1){
path.emplace_back(idx);
if(stopV and idx==v) break;
idx=heavyC(idx);
}
return path;
}
// Level Ancestor 頂点vの祖先であって深さdにある頂点番号を返す
// O(logN)
int LA(int v,int d) const {
assert(dep[v]>=d);
while(dep[head[v]]>d){
v=par[head[v]];
}
return vertex[id[v]-(dep[v]-d)];
}
// Lowest Common Ancestor 頂点u,vの最近共通祖先なる頂点番号を返す
// O(logN)
int LCA(int u,int v) const {
while(!same(u,v)){
if(id[u]>id[v]) std::swap(u,v);
v=par[head[v]];
}
return (id[u] < id[v] ? u:v);
}
// 任意の2頂点u,vの距離を返す O(logN)
int dist(int u,int v) const {
const int w=LCA(u,v);
return (dep[u]-dep[w])+(dep[v]-dep[w]);
}
// Jump on Tree 2頂点s,t及び非負整数iについて、
// パスstにおけるi番目の頂点番号を返す O(logN)
int jump(int u,int v,int i) const {
const int w=LCA(u,v);
const int d=(dep[u]-dep[w])+(dep[v]-dep[w]);
if(d<i) return -1;
if(i < dep[u]-dep[w]) return LA(u,dep[u]-i);
return LA(v,dep[v]-(d-i));
}
};
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int N;
cin>>N;
vector G(N,vector<int>());
for(int i=0;i<N-1;i++){
int u,v;
cin>>u>>v;
u--,v--;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
HeavyLightDecomposition HLD(G);
struct node1{
long val,len;
};
auto op1=[](node1 a,node1 b){ return node1(a.val+b.val,a.len+b.len); };
auto e1=[]{ return node1(0l,0l); };
auto mapping1=[](long f,node1 x){ return node1(x.val+x.len*f,x.len); };
auto composition1=[](long f,long g){ return f+g; };
auto id1=[]{ return 0l; };
vector<node1> ini1(N,node1(0,1));
atcoder::lazy_segtree<node1,op1,e1,long,mapping1,composition1,id1> seg(ini1);
int Q;
cin>>Q;
// vector<int> cnt(N);
// for(int i=0;i<N;i++){
// cout<<i<<" \n"[i+1==N];
// }
// for(int i=0;i<N;i++){
// cout<<HLD.toSeq(i)<<" \n"[i+1==N];
// }
// for(int i=0;i<N;i++){
// cout<<HLD.parent(i)<<" \n"[i+1==N];
// }
// for(int i=0;i<N;i++){
// cout<<HLD.heavyR(i)<<" \n"[i+1==N];
// }
while(Q--){
int a,b;
cin>>a>>b;
a--,b--;
// bool found=false;
// auto dfs=[&](this auto dfs,int p,int par=-1) -> void {
// if(p==b){
// found=true;
// cnt[HLD.toSeq(p)]++;
// return;
// }
// for(auto q:G[p]) if(q!=par){
// dfs(q,p);
// if(found){ cnt[HLD.toSeq(p)]++; break; }
// }
// if(p==a) found=false;
// };
// dfs(a);
while(!HLD.same(a,b)){
HLD.normalizePair(a,b);
const int r=HLD.heavyR(b);
seg.apply(HLD.toSeq(r),HLD.toSeq(b)+1,1);
b=HLD.parent(r);
// cout<<a<<" "<<b<<" "<<HLD.toSeq(a)<<" "<<HLD.toSeq(b)<<" "<<HLD.heavyR(a)<<" "<<HLD.heavyR(b)<<"\n";
}
HLD.normalizePair(a,b);
seg.apply(HLD.toSeq(a),HLD.toSeq(b)+1,1);
// cout<<"!"<<a<<" "<<b<<" "<<HLD.toSeq(a)<<" "<<HLD.toSeq(b)<<"\n";
// for(int i=0;i<N;i++) cout<<seg.get(i).val<<" \n"[i+1==N];
// for(int i=0;i<N;i++) cout<<cnt[i]<<" \n"[i+1==N];
// long aa{};
// for(int i=0;i<N;i++){
// aa+=seg.get(i).val*(seg.get(i).val+1)/2;
// }
// long bb{};
// for(int i=0;i<N;i++) bb+=cnt[i]*(cnt[i]+1)/2;
// cout<<aa<<" "<<bb<<"\n";
}
long ans{};
for(int i=0;i<N;i++){
const long val=seg.get(i).val;
ans+=val*(val+1)/2;
}
cout<<ans<<"\n";
// long a{};
// for(int i=0;i<N;i++) a+=long(cnt[i])*(cnt[i]+1)/2;
// cout<<a<<"\n";
}