結果

問題 No.399 動的な領主
ユーザー pazzle1230pazzle1230
提出日時 2018-07-14 01:17:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 801 ms / 2,000 ms
コード長 5,510 bytes
コンパイル時間 2,156 ms
コンパイル使用メモリ 187,800 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2024-04-17 11:48:24
合計ジャッジ時間 10,113 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 50 ms
5,376 KB
testcase_06 AC 772 ms
20,352 KB
testcase_07 AC 747 ms
20,352 KB
testcase_08 AC 757 ms
20,608 KB
testcase_09 AC 739 ms
20,480 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 33 ms
5,376 KB
testcase_12 AC 489 ms
20,992 KB
testcase_13 AC 477 ms
20,864 KB
testcase_14 AC 181 ms
22,400 KB
testcase_15 AC 266 ms
22,272 KB
testcase_16 AC 347 ms
21,888 KB
testcase_17 AC 779 ms
20,608 KB
testcase_18 AC 801 ms
20,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class HLDecomposition{
private:
	vector<vector<int32>> G;
	vector<int32> vid, inv, dep, par, typ, sub, head, in, out;
	int32 n, pos;
public:
	HLDecomposition(){}
	HLDecomposition(int32 n):
		n(n), pos(0), G(n), vid(n, -1), inv(n), dep(n, -1),
		par(n), typ(n), sub(n, 1), head(n), in(n, -1), out(n, -1){}

	void add_edge(int32 u, int32 v){
		G[u].push_back(v);
		G[v].push_back(u);
	}

	void build(){
		int32 type = 0;
		for(int32 i = 0;i < n;i++){
			if(dep[i] == -1){
				dfs(i);
				dfs2(i, type++);
			}
		}
	}

	void dfs(int32 v){
		using T = pair<int32, int32>;
		dep[v] = 0;
		par[v] = -1;
		stack<T> st;
		st.emplace(v, 0);
		while(st.size()){
			v = st.top().first;
			int32 &i = st.top().second;
			if(i<G[v].size()){
				int32 u = G[v][i++];
				if(u == par[v]) continue;
				par[u] = v;
				dep[u] = dep[v]+1;
				st.emplace(u, 0);
			}else{
				st.pop();
				for(int32 &u : G[v]){
					if(u == par[v]) continue;
					sub[v] += sub[u];
					if(G[v][0] == par[v] || sub[u] > sub[0]){
						swap(u, G[v][0]);
					}
				}
			}
		}
	}

	void dfs2(int32 v, int32 t){
		using T = tuple<int32, int32, int32>;
		stack<T> st;
		st.emplace(v, 0, v);
		while(st.size()){
			v = get<0>(st.top());
			int32 &i = get<1>(st.top());
			int32 h = get<2>(st.top());
			if(i == 0){
				typ[v] = t;
				in[v] = pos;
				out[v] = in[v]+sub[v]-1;
				vid[v] = pos++;
				inv[vid[v]] = v;
				head[v] = h;
			}
			if(i<G[v].size()){
				int32 u = G[v][i++];
				if(u == par[v]) continue;
				if(u == G[v][0])
					st.emplace(u, 0, h);
				else
					st.emplace(u, 0, u);
			}else{
				st.pop();
			}
		}
	}

	void for_each(int32 u, int32 v, const function<void(int32, int32)>& f){
		while(1){
			if(vid[u] > vid[v]) swap(u, v);
			f(max(vid[head[v]], vid[u]), vid[v]);
			if(head[u] != head[v]) v=par[head[v]];
			else break;
		}
	}

	void for_each_edge(int32 u, int32 v, const function<void(int32, int32)>& f){
		while(1){
			if(vid[u] > vid[v]) swap(u, v);
			if(head[u] != head[v]){
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			}else{
				if(u!=v) f(vid[u]+1, vid[v]);
				break;
			}
		}
	}

	void for_subtree(int32 u, const function<void(int32, int32)>& f){
		if(in[u] == -1){
			cout << "Invalid vertex." << endl;
			return;
		}
		f(in[u], out[u]);
	}

	int32 lca(int32 u, int32 v){
		while(1){
			if(vid[u] > vid[v]) swap(u, v);
			if(head[u] != head[v]) v = par[head[v]];
			else return u;
		}
	}

	int32 distance(int32 u, int32 v){
		return dep[u]+dep[v]-2*dep[lca(u, v)];
	}

	int32 getvid(int32 v){
		return vid[v];
	}
};

template<typename T, typename E>
class LazySegTree{
private:
	using F = function<T(T, T)>;
	using G = function<T(T, E)>;
	using H = function<E(E, E)>;
	using P = function<E(E, int64)>;
	int32 n;
	vector<T> node;
	vector<E> lazy;
	F f;
	G g;
	H h;
	P p;
	T ti;
	E ei;
public:
	LazySegTree(){}
	LazySegTree(int32 _n, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){
		init(_n);
	}

	LazySegTree(vector<T> v, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){
		init(v.size());
		for(int32 i = 0;i < v.size();i++) node[i+n-1] = v[i];
		for(int32 i = n-2;i >= 0;i--) node[i] = merge(node[i*2+1], node[i*2+2]);
	}

	void init(int32 _n){
		n = 1;
		while(n < _n) n*=2;
		node.resize(2*n-1, ti);
		lazy.resize(2*n-1, ei);
	}

	inline T merge(T lhs, T rhs){
		if(lhs == ti) return rhs;
		else if(rhs == ti) return lhs;
		return f(lhs, rhs);
	}

	inline void eval(int32 k, int32 l, int32 r){
		if(lazy[k] == ei) return;
		node[k] = g(node[k], p(lazy[k], r-l));
		if(r-l > 1){
			lazy[k*2+1] = h(lazy[k*2+1], lazy[k]);
			lazy[k*2+2] = h(lazy[k*2+2], lazy[k]);
		}
		lazy[k] = ei;
	}

	T update(int32 a, int32 b, E x, int32 k=0, int32 l=0, int32 r=-1){
		if(r<0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return node[k];
		if(a <= l && r <= b){
			lazy[k] = h(lazy[k], x);
			return g(node[k], p(lazy[k], r-l));
	}
		return node[k] = merge(update(a, b, x, k*2+1, l, (l+r)/2), update(a, b, x, k*2+2, (l+r)/2, r));
	}

	T query(int32 a, int32 b, int32 k=0, int32 l=0, int32 r=-1){
		if(r<0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return ti;
		if(a <= l && r <= b) return node[k];
		return merge(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
	}
};

int main(void){
	int32 N, Q;
	cin >> N;
	HLDecomposition hld(N);
	LazySegTree<int64, int64> lsg(N,
		[](int64 a, int64 b){return a+b;},
		[](int64 a, int64 b){return a+b;},
		[](int64 a, int64 b){return a+b;}, 0, 0);
	REP(i, N-1){
		int32 u, v;
		cin >> u >> v;
		u--; v--;
		hld.add_edge(u, v);
	}
	hld.build();
	cin >> Q;

	auto f = [&](int32 u, int32 v){
		lsg.update(u, v+1, 1);
	};

	REP(i, Q){
		int32 A, B;
		cin >> A >> B; A--; B--;
		hld.for_each(A, B, f);
	}
	int64 res = 0;
	REP(i, N){
		int64 x = lsg.query(i, i+1);
		res += x*(x+1)/2;
	}
	cout << res << endl;
}
0