結果

問題 No.399 動的な領主
ユーザー 小高悠太郎
提出日時 2025-09-05 01:09:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 840 ms / 2,000 ms
コード長 2,631 bytes
コンパイル時間 3,920 ms
コンパイル使用メモリ 300,036 KB
実行使用メモリ 41,176 KB
最終ジャッジ日時 2025-09-05 01:10:02
合計ジャッジ時間 12,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); ++i)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define fore(i, a) for(auto &i:a)
using ll = long long;
#include<atcoder/lazysegtree>
using namespace atcoder;

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


int main(){
  ll n; cin >> n;
	vector<vector<ll>> g(n), G(n);
	rep(i, n-1){
		ll u, v;
		cin >> u >> v;u--;v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	function<void(ll, ll)> dfs = [&](ll x, ll last){
		fore(to, G[x]){
			if(to == last)continue;
			g[x].push_back(to);
			dfs(to, x);
		}
	};
	dfs(0, -1);

  vector<ll> top(n), depth(n), parent(n), pos(n), cnt(n), order(n);
	depth[0] = 0;
	function<void(ll)> dfs1 = [&](ll x){
		cnt[x] = 1;
		fore(i, g[x]){
			depth[i] = depth[x]+1;
			parent[i] = x;
			dfs1(i);
			cnt[x]+=cnt[i];
		}
    fore(i, g[x]){
			if(cnt[i] > cnt[g[x][0]]){
				swap(i, g[x][0]);
			}
		}
	};
	dfs1(0);
  ll count = 0;  
	function<void(ll, bool)> dfs2 = [&](ll x, bool is_new){
		order[x] = count++;
		if(is_new){
			top[x] = x;
			pos[x] = 0;
		}
		else{
			top[x] = top[parent[x]];
			pos[x] = pos[parent[x]]+1;
		}
		rep(i, g[x].size()){
			if(i == 0){
				dfs2(g[x][i], false);
			}
			else{
				dfs2(g[x][i], true);
			}
		}
	};
	dfs2(0, true);
	vector<S> vec(n, {1, 1});
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(vec);
	function<void(ll,ll,ll)> ap = [&](ll l, ll r , ll w){
		if(top[l] == top[r]){
			if(pos[r] < pos[l])swap(l, r);
			seg.apply(order[l], order[r]+1, F{w});
		}
		else{
			if(depth[top[r]] > depth[top[l]])swap(l, r);
			seg.apply(order[top[l]], order[l]+1, F{w});
			l = parent[top[l]];
			ap(l, r, w);
		}
	};

	function<S(ll,ll)> pr = [&](ll l, ll r) -> S{
		if(top[l] == top[r]){
			if(pos[r] < pos[l])swap(l, r);
			return seg.prod(order[l], order[r]+1);
		}
		else{
			if(depth[top[r]] > depth[top[l]])swap(l, r);
			return op(seg.prod(order[top[l]], order[l]+1), pr(parent[top[l]], r));
		}
	};

	ll q; cin >> q;
	vector<tuple<ll,ll>> querys(q);
	rep(qq, q){
		ll a, b;
		cin >> a >> b;a--;b--;
		querys[qq] = {a, b};
	}
  ll ans = 0;
	rep(qq, q){
		auto[a, b] = querys[qq];
		ans += pr(a, b).value;
		ap(a, b, 1);
	}
  cout << ans << endl;
}
0