QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#220557#7608. Cliquesucup-team2303#RE 4ms20012kbC++143.7kb2023-10-20 15:20:232023-10-20 15:20:23

Judging History

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

  • [2023-10-20 15:20:23]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:20012kb
  • [2023-10-20 15:20:23]
  • 提交

answer

/*
    长弓背负,仙女月鹫,
	梦中徐来,长夜悠悠。
	今宵共君,夜赏囃子,
	盼君速归,长夜悠悠。
	睡意袭我,眼阖梦徭,
	睡意袭我,意归襁褓。
	手扶卓揭,仙女水狃,
	盼君速归,长夜悠悠。
	今宵共君,戏于西楼,
	盼君速归,长夜悠悠。
	睡意袭我,涟锜池留,
	睡意袭我,意归海角。
					                  ——《ever17》
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define pb push_back
#define pii pair<int, int>
inline int read()
{
	int sum = 0, nega = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0')
	{
	    if (ch == '-') nega = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * nega;
}
const int N = 2e5 + 9, mod = 1e9 + 7;
int to[N], head[N], nxt[N], cnt, n, m, rt;
int val[N], a[N];
int siz[N], son[N], top[N], dep[N];
int dfn[N], fa[N], tim;
inline void addedge(int u, int v)
{
	to[++cnt] = v; nxt[cnt] = head[u], head[u] = cnt;
}
inline void dfs1(int u, int f)
{
	fa[u] = f; dep[u] = dep[f] + 1; siz[u] = 1;
	for (int i = head[u]; i; i = nxt[i])
		if(to[i] != f)
		{
			dfs1(to[i], u);
			if(siz[son[u]] < siz[to[i]]) son[u] = to[i];
			siz[u] += siz[to[i]];
		}
}
inline void dfs2(int u, int topf)
{
	dfn[u] = ++tim;
	top[u] = topf;
	if(son[u]) dfs2(son[u], topf);
	for (int i = head[u]; i; i = nxt[i])
		if(to[i] != son[u] && to[i] != fa[u]) dfs2(to[i], to[i]);
}
int tr[N << 2], tag[N << 2], inv2 = (mod + 1) / 2;
inline int lc(int p) {return p << 1;}
inline int rc(int p) {return p << 1 | 1;}
inline void push_up(int p) {tr[p] = (tr[lc(p)] + tr[rc(p)]) % mod; return ;}
inline void push_down(int p)
{
	if(tag[p] != 1)
	{
		tag[lc(p)] = tag[lc(p)] * tag[p] % mod;
		tag[rc(p)] = tag[rc(p)] * tag[p] % mod;
		tr[lc(p)] = tr[lc(p)] * tag[p] % mod;
		tr[rc(p)] = tr[rc(p)] * tag[p] % mod; tag[p] = 1; return ;
	} return ;
}
inline void build(int l, int r, int p)
{
	tag[p] = 1;
	if(l == r) {tr[p] = tag[p] = 1; return ;}
	int mid = (l + r) >> 1;
	build(l, mid, lc(p)); build(mid + 1, r, rc(p));
	push_up(p); return ;
}
inline void update(int l, int r, int p, int L, int R, int v)
{
	if(L > R) return ;
	if(L <= l && r <= R) {tr[p] = tr[p] * v % mod, tag[p] = tag[p] * v % mod;return ;}
	int mid = (l + r) >> 1;
	push_down(p);
	if(mid >= L) update(l, mid, lc(p), L, R, v);
	if(mid < R) update(mid + 1, r, rc(p), L, R, v);
	push_up(p); return ;
}
inline int update_chain(int x, int y, int v)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		update(1, n, 1, dfn[top[x]], dfn[x], v);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	update(1, n, 1, dfn[x], dfn[y], v);
	return x;
}
int ans[N];
char opt[8];
struct node
{
	int op, u, v;
}p[N];
signed main()
{
	n = read();
	for (int i = 1; i < n; i++)
	{
		int x = read(), y = read();
		addedge(x, y); addedge(y, x);
	}
	int q = read();
 	dfs1(1, 0); dfs2(1, 1);
 	build(1, n, 1);
 	L(i, 1, q)
 	{
 		scanf("%s", opt + 1);
 		int u = read(), v = read();
 		if(opt[1] == '+') p[i] = node{1, u, v}, update_chain(u, v, 2);
 		else p[i] = node{2, u, v}, update_chain(u, v, inv2);
 		ans[i] = tr[1];
	}
	build(1, n, 1);
	L(i, 1, q)
	{
		int t, u = p[i].u, v = p[i].v;
		if(p[i].op == 1)
		{
			t = update_chain(u, v, 2); update(1, n, 1, dfn[t], dfn[t], inv2);
		}
		else
		{
			t = update_chain(u, v, inv2); update(1, n, 1, dfn[t], dfn[t], 2);
		}
		ans[i] = (ans[i] - tr[1] + mod) % mod;
	}
	L(i, 1, q) printf("%lld\n", ans[i] % mod);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 4ms
memory: 20012kb

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
257
255
259
515
1027
1283
643
385
769
1537
769
785
865
481
737
369

result:

ok 30 lines

Test #3:

score: -100
Runtime Error

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:


result: