QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302488#7608. Cliquesdefyers#TL 3ms77336kbC++203.9kb2024-01-10 22:12:372024-01-10 22:12:38

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 22:12:38]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:77336kb
  • [2024-01-10 22:12:37]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using ll = long long;
using LL = long long;
using pii = pair<int, int>;

const int N = 5e5 + 11;
const int LGN = 20;
int p[N], sz[N], dep[N], dfn[N], id = 0, head[N], anc[LGN][N];

vector<int> G[N], ch[N];

void dfs0(int v, int pa = -1){
	if(pa == -1){
		p[v] = v; for(int j = 0; j < LGN; j++) anc[j][v] = v;
	}
	sz[v] = 1;
	for(auto u : G[v]){
		if(u == pa) continue;

		anc[0][u] = p[u] = v;
		for(int j = 1; j < LGN; j++)
			anc[j][u] = anc[j - 1][anc[j - 1][u]];
		dep[u] = dep[v] + 1;

		dfs0(u, v); sz[v] += sz[u];
		ch[v].push_back(u);
	}
	sort(ch[v].begin(), ch[v].end(), [](auto x, auto y){
		return sz[x] > sz[y];
	});
}

void dfs1(int v, int h){
	// cout << "DFS1 " << v << ' ' << h << endl;
	head[v] = h;
	if(ch[v].size()){
		int u = ch[v][0];
		dfn[u] = ++id;
		dfs1(u, v == 0 ? dfn[u] : h);
	}
	for(int i = 1; i < ch[v].size(); i++){
		int u = ch[v][i];
		dfn[u] = ++id;
		dfs1(u, dfn[u]);
	}
}

int kth_anc(int v, int k){
	for(int j = LGN - 1; j >= 0; j--){
		if((1 << j) & k) v = anc[j][v];
	}
	return v;
}

int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v); u = kth_anc(u, dep[u] - dep[v]);
	for(int j = LGN - 1; j >= 0; j--){
		if(anc[j][u] != anc[j][v])
			u = anc[j][u], v = anc[j][v];
	}
	return u == v ? u : p[u];
}

#define int long long
const int MOD = 1e9 + 7;
int mi2 = (MOD + 1) / 2;

int n; 

void chmul(int& x, int y){
	x = (x * y) % MOD;
}
struct SegTree{
	int t[N << 2], lz[N << 2];
	void init(int v = 0, int l = 1, int r = n){
		lz[v] = 1;
		if(l == r) t[v] = 1;
		else {
			int m = (l + r) / 2;
			init(v * 2 + 1, l, m);
			init(v * 2 + 2, m + 1, r);
			t[v] = (t[v * 2 + 1] + t[v * 2 + 2]) % MOD;
		}
	}

	void push(int v){
		if(lz[v] != 1){
			chmul(lz[v * 2 + 1], lz[v]);
			chmul(lz[v * 2 + 2], lz[v]);
			chmul(t[v * 2 + 1], lz[v]);
			chmul(t[v * 2 + 2], lz[v]);
			lz[v] = 1;
		}
	}
	void update(int ql, int qr, int qv, int v = 0, int l = 1, int r = n){
		// if(v == 0) printf("UPDATE %lld %lld %lld\n", ql, qr, qv);
		if(qr < l || r < ql || qr < ql) return;
		if(ql <= l && r <= qr) t[v] = (t[v] * qv) % MOD, lz[v] = (lz[v] * qv) % MOD;
		else {
			int m = (l + r) / 2; push(v);
			update(ql, qr, qv, v * 2 + 1, l, m);
			update(ql, qr, qv, v * 2 + 2, m + 1, r);
			t[v] = (t[v * 2 + 1] + t[v * 2 + 2]) % MOD;
		}
	}
	int qry(){
		return t[0];
	}
};

struct HLD{
	SegTree ST;
	void init(){
		ST.init();
	}
	void add(int v, int l, int inc){
		int mul = inc == 1 ? 2 : mi2;
		while(head[v] != head[l]){
			ST.update(dfn[head[v]], dfn[v], mul);
			v = p[head[v]];
		}
		ST.update(dfn[l], dfn[v], mul);
	}
	int qry(){
		return ST.qry();
	}
} HLD0, HLD1;

void solve(int TC) {
	cin >> n;
	G[0].push_back(1);
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs0(0); dfs1(0, 0);
	// for(int i = 1; i <= n; i++) cout << dfn[i] << ' '; cout << '\n';
	// for(int i = 1; i <= n; i++) cout << head[i] << ' '; cout << '\n';
	HLD0.init(), HLD1.init();
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		char op; cin >> op; int u, v; cin >> u >> v;
		int l = lca(u, v);
#ifdef LOCAL
		cout << "LCA: " << l << ' ' << u << ' ' << v << endl;
#endif
		int inc = op == '+' ? 1 : -1;
		int pu = kth_anc(u, dep[u] - dep[l] - 1);
		int pv = kth_anc(v, dep[v] - dep[l] - 1);
		if(u != l) HLD0.add(u, pu, inc), HLD1.add(u, pu, inc);
		if(v != l) HLD0.add(v, pv, inc), HLD1.add(v, pv, inc);
		HLD0.add(l, l, inc);
		int a = HLD0.qry();
		int b = HLD1.qry();
		int ans = ((a - b) % MOD + MOD) % MOD;
		cout << ans << '\n';
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 77336kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

score: -100
Time Limit Exceeded

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:


result: