#1190816 (C++23(gnu拡張)) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: ふぃぼん
• 提出日時: 2026-09-30 14:57:19
• 言語: C++23(gnu拡張) (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 833 ms / 2,000 ms
• コード長: 3,335 bytes
• コンパイル時間: 7,049 ms
• コンパイル使用メモリ: 387,392 KB
• 実行使用メモリ: 29,232 KB
• 最終ジャッジ日時: 2026-09-30 14:57:40
• 合計ジャッジ時間: 15,752 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
other	AC * 19

ソースコード

#if __has_include(<acl_bits.hpp>)
#include <acl_bits.hpp>
#else
#include <bits/stdc++.h>
#include <atcoder/all>
#endif
using namespace atcoder;
using namespace std;
using ll=long long;
using ld=long double;
using P = pair<ll,ll>;
using TUP = tuple<ll,ll,ll>;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for (int i = (n-1); i >= 0; --i)
template<typename t,typename u>inline bool chmax(t&a,u b){return a<b?a=b,1:0;}
template<typename t,typename u>inline bool chmin(t&a,u b){return a>b?a=b,1:0;}
inline int yn(bool b){cout<<(b?"Yes\n":"No\n");return 0;}
const vector<int> di={1,0,-1,0},dj={0,1,0,-1};
using mint = modint998244353;
inline ostream&operator<<(ostream&os,const mint& x){os<<x.val();return os;};
template <typename t>ostream&operator<<(ostream&os,const vector<t>&x){for(t i:x)os<<i<<' ';return os;}
template <typename t>ostream&operator<<(ostream&os,const vector<vector<t>>&x){for(const vector<t>&i:x)os<<i<<'\n';return os;}
const ll inf=2e18;

struct hld{
	int n;
	vector<int> vertex,id,head,par,dep;
	hld(vector<vector<int>> g){
		n=g.size();
		id.resize(n);
		head.resize(n);
		par.resize(n);
		dep.resize(n);
		{
			auto f=[&](auto f,int x,int px)->int{
				int cnt=1,mx=0;
				rep(i,g[x].size()){
					int nx=g[x][i];
					if(nx==px)continue;
					int s=f(f,nx,x);
					cnt+=s;
					if(chmax(mx,s))swap(g[x][0],g[x][i]);
				}
				return cnt;
			};
			f(f,0,0);
		}
		{
			auto f=[&](auto f,int x,int px)->void{
				id[x]=vertex.size();
				vertex.push_back(x);
				for(int nx:g[x])if(px!=nx){
					par[nx]=x;
					dep[nx]=dep[x]+1;
					head[nx]=(nx==g[x][0]?head[x]:nx);
					f(f,nx,x);
				}
			};
			f(f,0,0);
		}
	}
	int lca(int u,int v){
		while(head[u]!=head[v]){
			if(id[u]>id[v])u=par[head[u]];
			else v=par[head[v]];
		}
		return id[u]<id[v]?u:v;
	}
	int dist(int u,int v){
		int c=lca(u,v);
		return dep[u]+dep[v]-2*dep[c];
	}
	int level_ancestor(int u,int d){
		if(dep[u]<d)return -1;
		while(dep[head[u]]>d){
			u=par[head[u]];
		}
		return vertex[id[u]-(dep[u]-d)];
	}
	int jump_up(int u,int steps){
		return level_ancestor(u,dep[u]-steps);
	}
	int jump(int u,int v,int steps){
		int c=lca(u,v);
		int uc=dep[u]-dep[c];
		int vc=dep[v]-dep[c];
		if(steps < uc)return jump_up(u,steps);
		else if(steps-uc<=vc)return jump_up(v,uc+vc-steps);
		else return -1;
	}
	template<typename F> // TODO:可換な演算じゃない場合も成立するようにする
	void foreach(int u,int v,const F& f,bool on_edge=0){
		while(head[u]!=head[v]){
			if(id[u]<id[v])swap(u,v);
			f(id[head[u]],id[u]+1);
			u=par[head[u]];
		}
		if(id[u]<id[v])swap(u,v);
		f(id[v]+on_edge,id[u]+1);
	}
};

struct S{
    long long value;
    int size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
	int n;
	cin>>n;
	vector<vector<int>> g(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u--,v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	hld hl(g);
	ll ans=0;
	vector<S> v(n,{0,1});
	lazy_segtree<S,op,e,F,mapping,composition,id> seg(v);

	int q;
	cin>>q;
	rep(qi,q){
		int a,b;
		cin>>a>>b;
		a--,b--;
		hl.foreach(a,b,[&](int l,int r){
				seg.apply(l,r,1);
				ans+=seg.prod(l,r).value;
				});
	}
	cout<<ans<<endl;
}