UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185669#2376. 树与异或tkswls1003075ms48132kbC++111.2kb2023-09-30 09:56:172023-09-30 12:13:57

answer

#include<bits/stdc++.h>
using namespace std;
int n, m, val[1000006], head[1000006], nxt[2000006], to[2000006], ccnt, fa[1000006], ffa[1000006], sum[1000006], ssum[1000006];
long long ans[1000006], cnt;
const long long mod = 1000000007;
inline void add(int p, int q) {
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	head[p] = ccnt;
}
inline void dfs(int p) {
	sum[fa[p]] ^= val[p];
	sum[ffa[p]] ^= val[p];
	ssum[fa[p]] ^= val[p];
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != fa[p]) {
			fa[to[i]] = p;
			ffa[to[i]] = fa[p];
			dfs(to[i]);
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
	}
	int p, q;
	for (int i = 1; i < n; i++) {
		cin >> p >> q;
		add(p, q);
		add(q, p);
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		cin >> p >> q;
		ssum[fa[p]] ^= val[p];
		sum[fa[p]] ^= val[p];
		sum[ffa[p]] ^= val[p];
		val[p] = q;
		ssum[fa[p]] ^= val[p];
		sum[fa[p]] ^= val[p];
		sum[ffa[p]] ^= val[p];
		ans[i] = (sum[p] ^ ssum[fa[p]] ^ val[fa[p]] ^ val[ffa[p]]);
		cnt += ((ans[i] * i) % mod * i) % mod;
		cnt %= mod;
	}
	cout << cnt;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1340kb

input:

1000 994
780089107 4670366 871010085 73730768 526852049 572589363 885190993 1049357301 450850404 460...

output:

503748432

result:

ok 1 number(s): "503748432"

Test #2:

score: 10
Accepted
time: 1ms
memory: 1340kb

input:

1000 999
26885995 181771373 378079250 245122183 660787775 479226046 575400611 257120086 214404794 48...

output:

301019013

result:

ok 1 number(s): "301019013"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1340kb

input:

1000 994
978408146 31636243 945016735 512129400 92881624 689719983 649699545 964802847 100094796 941...

output:

250985726

result:

ok 1 number(s): "250985726"

Test #4:

score: 10
Accepted
time: 41ms
memory: 5972kb

input:

100000 99994
194640838 777315353 114710204 754050649 372592717 210279787 542056883 638262010 7998293...

output:

897014293

result:

ok 1 number(s): "897014293"

Test #5:

score: 10
Accepted
time: 40ms
memory: 5976kb

input:

100000 100000
458877901 215980825 777376132 863774865 34430451 828397116 94813690 931300514 10548367...

output:

351450518

result:

ok 1 number(s): "351450518"

Test #6:

score: 10
Accepted
time: 61ms
memory: 5976kb

input:

100000 99991
56406146 757409402 876799234 573444553 883023109 326033134 328116703 623771278 41269529...

output:

440189625

result:

ok 1 number(s): "440189625"

Test #7:

score: 10
Accepted
time: 706ms
memory: 48116kb

input:

1000000 999998
814298729 663807029 628693441 45635199 148428014 913833778 1034283337 600802841 58045...

output:

447637970

result:

ok 1 number(s): "447637970"

Test #8:

score: 10
Accepted
time: 673ms
memory: 48132kb

input:

1000000 999993
112899321 425466951 471078924 857561298 449437156 710041336 1033281580 23390934 44420...

output:

449713864

result:

ok 1 number(s): "449713864"

Test #9:

score: 10
Accepted
time: 763ms
memory: 48132kb

input:

1000000 1000000
273043260 1042513348 30746190 864557483 187812119 562837674 263192174 364182254 3537...

output:

922464355

result:

ok 1 number(s): "922464355"

Test #10:

score: 10
Accepted
time: 790ms
memory: 48116kb

input:

1000000 999995
83067658 1064735371 623243759 757522311 539363923 924297206 75317137 543750195 822898...

output:

318242296

result:

ok 1 number(s): "318242296"

Extra Test:

score: 0
Extra Test Passed