QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222906#7608. Cliquesucup-team191#WA 3ms20360kbC++143.5kb2023-10-21 19:37:052023-10-21 19:37:06

Judging History

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

  • [2023-10-21 19:37:06]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:20360kb
  • [2023-10-21 19:37:05]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 2e5 + 500;
const int LOG = 18;
const int MOD = 1e9 + 7;
const int OFF = 1 << 18;

inline int add(int A, int B) {
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B) {
	if(A - B < 0) return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B) {
	return (ll)A * B % MOD;
}

inline int pot(int A, int B) {
	int ret = 1, bs = A;
	for(; B ; B >>= 1) {
		if(B & 1) ret = mul(ret, bs);
		bs = mul(bs, bs);
	}
	return ret;
}

int ind[N], siz[N], par[N][LOG], hat[N], dep[N], pot2[N], kof[2 * OFF];
vector < int > v[N];
int tme;

int prop[2 * OFF], T[2 * OFF], imp[N], n;

void refresh(int x) {
	if(prop[x] == 1) return;
	T[x] = mul(T[x], prop[x]);
	if(x < OFF) {
		prop[2 * x] = mul(prop[2 * x], prop[x]);
		prop[2 * x + 1] = mul(prop[2 * x + 1], prop[x]);
	}
	prop[x] = 1;
}

void range_update(int i, int a, int b, int lo, int hi, int x) {
	if(lo <= a && b <= hi) {
		prop[i] = mul(prop[i], x); refresh(i); return;
	}
	if(a > hi || b < lo) return;
	range_update(2 * i, a, (a + b) / 2, lo, hi, x);
	range_update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
	if(2 * i < OFF) T[i] = add(T[2 * i], T[2 * i + 1]);
	else T[i] = add(mul(T[2 * i], kof[2 * i]), mul(T[2 * i + 1], kof[2 * i + 1]));
}


void precompute(){
	pot2[0] = 1;
	for(int i = 1;i < N;i++)
		pot2[i] = add(pot2[i - 1], pot2[i - 1]);
}

bool cmp(int x, int y) {
	return siz[x] > siz[y];
}

void dfs_siz(int x, int lst){
	siz[x] = 1; par[x][0] = lst;
	dep[x] = dep[lst] + 1;
	for(int y : v[x]) {
		if(y == lst) continue;
		dfs_siz(y, x);
		siz[x] += siz[y];
	}
}

void dfs(int x, int lst, int cur) {
	ind[x] = tme++; hat[x] = cur;
	int fir = 1;
	sort(v[x].begin(), v[x].end(), cmp);
	for(int y : v[x]) {
		if(y == lst) continue;
		dfs(y, x, fir ? cur : y);
		fir = 0;
	}
}

int digni(int x, int k) {
	for(int i = 0;i < LOG;i++)
		if(k & (1 << i)) x = par[x][i];
	return x;
}

int lca(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	a = digni(a, dep[a] - dep[b]);
	if(a == b) return a;
	for(int k = LOG - 1;k >= 0;k--)
		if(par[a][k] != par[b][k])
			a = par[a][k], b = par[b][k];
	return par[a][0];
}

void hld_path(int a, int b, int x) {
	while(dep[hat[a]] > dep[b]) {
		range_update(1, 0, OFF - 1, ind[hat[a]], ind[a], x);
		a = par[hat[a]][0];
	}
	range_update(1, 0, OFF - 1, ind[b], ind[a], x);
}

void add_path(int a, int b, int fl) {
	if(dep[a] < dep[b]) swap(a, b);
	int lc = lca(a, b);
	imp[lc] += fl ? 1 : -1; 
	kof[OFF + ind[lc]] = pot2[imp[lc]] - 1;
	range_update(1, 0, OFF - 1, ind[lc], ind[lc], 1);
	int fact = fl ? 2 : ((MOD + 1) / 2);
	if(a != b) {
		hld_path(a, digni(a, dep[a] - dep[lc] - 1), fact);
		if(b != lc) hld_path(b, digni(b, dep[b] - dep[lc] - 1), fact);
	} 
}



int main() {
	precompute();
	scanf("%d", &n);
	for(int i = 1;i < n;i++) {
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	dfs_siz(1, 1); dfs(1, 1, 1);
	for(int j = 1;j < LOG;j++)
		for(int i = 1;i <= n;i++)
			par[i][j] = par[par[i][j - 1]][j - 1];
	for(int i = 0;i < n;i++) T[OFF + i] = 1, prop[OFF + i] = 1;
	for(int i = OFF - 1; i ; i--) {
		prop[i] = 1;
	}
	int q; scanf("%d", &q);
	for(;q--;) {
		char ty; int a, b; scanf(" %c%d%d", &ty, &a, &b);
		add_path(a, b, ty == '+');
		printf("%d\n", T[1]);		
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Wrong Answer
time: 0ms
memory: 20204kb

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:

1
3
7
3
1
3
7
15
7
15
31
63
127
255
256
255
259
515
1027
1283
643
385
769
1537
769
773
833
449
833
369

result:

wrong answer 15th lines differ - expected: '257', found: '256'