結果

問題 No.399 動的な領主
コンテスト
ユーザー manjuuu_onsen
提出日時 2024-02-26 01:32:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 520 ms / 2,000 ms
コード長 3,691 bytes
コンパイル時間 2,192 ms
コンパイル使用メモリ 186,592 KB
実行使用メモリ 23,940 KB
最終ジャッジ日時 2024-09-29 11:31:49
合計ジャッジ時間 8,418 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:162:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  162 |                 for(auto [l,r]:s) {
      |                          ^

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<int,int>;

/*
☆HLDの使い方☆
まずbuildする
①頂点に値がある場合: 
	- 代入はseg[hld.in[v]] = a[v]
	- パスクエリはfor_each_vertex(u,v)
	- 部分木クエリは hld.in[v] ~ hld.out[v]で
②辺に値がある場合:
	- 代入(aとbの間の辺に重みw)は (par[a] == b ? seg[hld.in[a]] = w : seg[hld.in[b]] = w)
	- パスクエリはfor_each_edge(u, v)
非可換だと壊れると思う
*/

struct HLD {
	int n;
	vector<int> par,in,out,head,inv,sub;
	vector<vector<int>> g;
	HLD(){};
	HLD(int n) {
		g = vector<vector<int>>(n);
		sub = par = in = out = head = inv = vector<int>(n);
	}
	void add_edge(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int dfs_hld(int c, int p) {
		sub[c] = 1;
		if(p != -1) g[c].erase(find(g[c].begin(), g[c].end(), p));
		for(auto &d :g[c]) {
			par[d] = c;
			sub[c] += dfs_hld(d, c);
			if(sub[d] > sub[g[c][0]]) swap(d, g[c][0]);
		}
		return sub[c];
	}
	void dfs2(int c, int &i) {
		in[c] = i++;
		inv[in[c]] = c;
		for(auto &d : g[c]) {
			head[d] = (g[c][0] == d ? head[c] : d);
			dfs2(d,i);
		}
		out[c] = i;
	}
	void build(int r=0) {
		dfs_hld(0,-1);
		int cnt = 0;
		dfs2(0,cnt);
	}
	int lca(int u, int v) {
		while(1) {
			if(in[u] > in[v]) swap(u,v);
			if(head[u] == head[v]) return u;
			v = par[head[v]];
		}
	}
	vector<pair<int,int>> for_each_vertex(int u, int v) { //seg[in[u]] に代入
		vector<pair<int,int>> path;
		while(1) {
			if(in[u] > in[v]) swap(u,v);
			if(head[u] != head[v]) {
				path.push_back({in[head[v]], in[v] + 1});
				v = par[head[v]];
			}else {
				path.push_back({in[u],in[v]+1});
				return path;
			}
		}	
	}

	vector<pair<int,int>> for_each_edge(int u, int v) { //子に辺の情報を代入
		vector<P> path;
		while(1) {
			if(in[u] > in[v]) swap(u,v);
			if(head[u] != head[v]) {
				path.push_back({in[head[v]], in[v] + 1});
				v = par[head[v]];
			} else {
				path.push_back({in[u] + 1, in[v] + 1});
				return path;
			}
		}
	}
};

template<typename T>
struct fenwick_tree {
	int n;
	vector<T> bit;
	fenwick_tree(){};
	fenwick_tree(int n):n(n), bit(n+1,0){}
	void add(int i, T x) {
		i++;
		for(int idx=i; idx<=n; idx += (idx & (-idx))) bit[idx] += x;
	}
	T sum(int i) { 
		T s(0);
		for(int idx=i; idx>0; idx-= (idx & (-idx)) ) s += bit[idx];
		return s;
	}
	T sum(int l, int r) {return sum(r) - sum(l);}
	int lower_bound(T w) {
		if(w <= 0) return 0; 
		int x=0, r=1;
		while(r < n) r = r<<1;
		for(int len = r; len > 0; len = len>>1) {
			if(x + len < n && bit[x+len] < w) {
				w -= bit[x + len];
				x += len;
			}
		}
		return x+1;
	}
};

#include<atcoder/lazysegtree>
using namespace atcoder;
/*
☆atcoder::lazy_segtreeの使い方☆
<typename S, S (*op)(S, S), S (*e)(), typename F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> lazy_segtree
作用素の合成composition(F f, F g) は f∘gとなる(つまりfが後から来たもの)
↓↓↓↓↓↓区間和・区間加算
*/
struct S {
	ll x;
	int l;
};
S op(S a, S b){return {a.x + b.x, a.l + b.l};}
S e(){return {0,0};}
using F = ll;
S mapping(F f, S x) {return {x.x + x.l*f,x.l};}
F composition(F f, F g){return f + g;}
F id(){return 0;}

int main()
{
	int N;
	cin>>N;
	HLD hl(N);
	for(int i=0; i<N-1; i++) {
		int u,v;cin>>u>>v;
		u--,v--;
		hl.add_edge(u,v);	
	}
	hl.build();
	lazy_segtree<S,op,e,F,mapping,composition,id> seg(N);
	for(int i=0; i<N; i++) seg.set(i, {0,1});
	int Q;
	cin>>Q;
	ll ans = 0;
	while(Q--) {
		int u,v;cin>>u>>v;
		u--,v--;
		auto s = hl.for_each_vertex(u,v);
		for(auto [l,r]:s) {
			ans += seg.prod(l,r).x + (r - l);
			seg.apply(l,r,1);
		}
	}
	cout << ans << endl;
	
}
0