ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185669 | #2376. 树与异或 | tkswls | 100 | 3075ms | 48132kb | C++11 | 1.2kb | 2023-09-30 09:56:17 | 2023-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