#45845 (C++11) No.235 めぐるはめぐる (5)

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
ユーザー	pekempey
提出日時	2015-08-27 18:01:19
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2,275 ms / 10,000 ms
コード長	6,057 bytes
コンパイル時間	2,198 ms
コンパイル使用メモリ	186,580 KB
実行使用メモリ	103,304 KB
最終ジャッジ日時	2023-09-25 18:54:47
合計ジャッジ時間	11,722 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,275 ms 81,712 KB
testcase_01	AC	1,809 ms 103,304 KB
testcase_02	AC	2,085 ms 87,040 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i, a) rep2 (i, 0, a)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) repr2 (i, 0, a)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;
const int inf = 1e9;
const pair<int, int> infp(inf, inf);

const ll mod = 1e9 + 7;
ll modulo(ll x) {
	x %= mod; x += mod; x %= mod;
	return x;
}

template<class T>
struct RMQ {
	vector<T> seg;
	int size;
	T inf;
	RMQ() {}
	RMQ(int n, T inf) {
		init(n, inf);
	}
	void init(int n, T inf) {
		this->inf = inf;
		size = 1;
		while (size < n) size *= 2;
		seg.resize(size * 2 - 1, inf);
	}
	void update(int k, T x) {
		k += size - 1;
		seg[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return inf;
		if (a <= l && r <= b) return seg[k];
		T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	T query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

struct LCA {
	RMQ<pair<int, int>> rmq;
	vector<pair<int, int> > euler;
	vector<vector<int> > G;
	vector<int> id;
	LCA(int V) : rmq(V * 2 - 1, make_pair(inf, inf)), G(V), id(V), euler(V * 2 - 1) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void dfs(int curr, int prev, int depth, int &k) {
		id[curr] = k;
		euler[k++] = make_pair(depth, curr);
		for (int next : G[curr]) if (next != prev) {
			dfs(next, curr, depth + 1, k);
			euler[k++] = make_pair(depth, curr);
		}
	}
	void build() {
		int k = 0;
		dfs(0, -1, 0, k);
		rep (i, euler.size()) {
			rmq.update(i, euler[i]);
		}
	}
	int query(int u, int v) {
		return rmq.query(min(id[u], id[v]), max(id[u], id[v]) + 1).second;
	}
};

struct SegmentTree {
	vector<ll> sum, lazy;
	vector<ll> weight, wsum;
	int size;
	void init(int n) {
		size = 1;
		while (size < n) size *= 2;
		sum.resize(size * 2 - 1);
		lazy.resize(size * 2 - 1);
		weight.resize(size);
		wsum.resize(size + 1);
	}
	void setWeight(int k, int w) {
		weight[k] = w;
	}
	void buildWeight() {
		partial_sum(weight.begin(), weight.end(), wsum.begin() + 1);
		rep (i, wsum.size()) {
			wsum[i] %= mod;
		}
	}
	void setInit(int k, ll x) {
		k += size - 1;
		sum[k] = x;
	}
	void build() {
		repr (k, size - 1) {
			sum[k] = sum[k * 2 + 1] + sum[k * 2 + 2];
			sum[k] %= mod;
		}
	}
	void evallazy(int k, int l, int r) {
		sum[k] += lazy[k] * (wsum[r] - wsum[l]);
		sum[k] = modulo(sum[k]);
		if (r - l > 1) {
			lazy[k * 2 + 1] += lazy[k];
			lazy[k * 2 + 2] += lazy[k];
			lazy[k * 2 + 1] %= mod;
			lazy[k * 2 + 2] %= mod;
		}
		lazy[k] = 0;
	}
	void update(int a, int b, ll x, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			lazy[k] += x;
			lazy[k] %= mod;
			evallazy(k, l, r);
		} else {
			update(a, b, x, k * 2 + 1, l, (l + r) / 2);
			update(a, b, x, k * 2 + 2, (l + r) / 2, r);	
			sum[k] = sum[k * 2 + 1] + sum[k * 2 + 2];
			sum[k] %= mod;
		}
	}
	void update(int a, int b, ll x) {
		update(a, b, x, 0, 0, size);
	}
	ll query(int a, int b, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return 0;
		if (a <= l && r <= b) return sum[k];
		ll res = 0;
		res += query(a, b, k * 2 + 1, l, (l + r) / 2);
		res += query(a, b, k * 2 + 2, (l + r) / 2, r);
		return res % mod;
	}
	ll query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

int V;
vector<int> G[202020];
vector<int> color[202020]; // (0:light), (1:heavy)
int parent[202020];
int root[202020];
int order[202020];
int size[202020];
map<int, SegmentTree> seg;

ll S[202020], C[202020];

int dfs(int curr, int prev) {
	int res = 1;
	rep (i, G[curr].size()) {
		int next = G[curr][i];
		if (next == prev) continue;
		parent[next] = curr;
		int d = dfs(next, curr);
		res += d;
		color[curr][i] = d;
	}
	int maxi = max_element(color[curr].begin(), color[curr].end()) - color[curr].begin();
	rep (i, G[curr].size()) {
		color[curr][i] = maxi == i;
	}
	return res;
}

void dfs2(int curr, int prev) {
	rep (i, G[curr].size()) {
		int next = G[curr][i];
		if (next == prev) continue;
		if (color[curr][i]) {
			root[next] = root[curr];
			order[next] = order[curr] + 1;	
		}
		dfs2(next, curr);
	}	
}

void build() {
	memset(parent, -1, sizeof(parent));
	rep (i, V) color[i].resize(G[i].size());
	dfs(0, -1);
	rep (i, V) root[i] = i;
	dfs2(0, -1);
	rep (i, V) {
		size[root[i]]++;
	}
	rep (i, V) {
		if (i == root[i]) {
			seg[i].init(size[i]);
		}
	}
}

void update(LCA &lca, int u, int v, ll x) {
	int l = lca.query(u, v);
	while (root[l] != root[u]) {
		seg[root[u]].update(0, order[u] + 1, x);
		u = parent[root[u]];
	}
	while (root[l] != root[v]) {
		seg[root[v]].update(0, order[v] + 1, x);
		v = parent[root[v]];
	}
	int a = min(order[u], order[v]);
	int b = max(order[u], order[v]);
	seg[root[u]].update(a, b + 1, x);
}

int query(LCA &lca, int u, int v) {
	int l = lca.query(u, v);
	ll res = 0;
	while (root[l] != root[u]) {
		res += seg[root[u]].query(0, order[u] + 1);
		res %= mod;
		u = parent[root[u]];
	}
	while (root[l] != root[v]) {
		res += seg[root[v]].query(0, order[v] + 1);
		res %= mod;
		v = parent[root[v]];
	}
	int a = min(order[u], order[v]);
	int b = max(order[u], order[v]);
	res += seg[root[u]].query(a, b + 1);
	res %= mod;
	return res;
}

int main() {
	cin >> V;
	rep (i, V) cin >> S[i];
	rep (i, V) cin >> C[i];
	LCA lca(V);
	rep (i, V - 1) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
		lca.add(u, v);
	}
	lca.build();
	build();

	rep (i, V) {
		seg[root[i]].setWeight(order[i], C[i]);
		seg[root[i]].setInit(order[i], S[i]);
	}
	rep (i, V) {
		if (i == root[i]) {
			seg[i].buildWeight();
			seg[i].build();
		}
	}

	int Q;
	cin >> Q;
	while (Q--) {
		int a;
		cin >> a;
		if (a == 0) {
			int x, y, z;
			cin >> x >> y >> z;
			x--; y--;
			update(lca, x, y, z);
		} else {
			int x, y;
			cin >> x >> y;
			x--; y--;
			ll ans = query(lca, x, y);
			cout << ans << endl;
		}
	}

    return 0;
}

yukicoder

結果

テストケース

ソースコード