NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #214637 | #2376. 树与异或 | Invisible_H | 0 | 21ms | 25748kb | C++11 | 4.2kb | 2024-11-20 21:32:13 | 2024-11-20 23:08:25 |
answer
#include <bits/stdc++.h>
using namespace std;
const long long MX=1000100,INF=0x3f3f3f3f,MO=1e9+7;
vector<long long>vec[MX];
long long f[MX][3],fath[MX];
long long n;bool vis[MX],fg;
void dfs(long long now,long long fa){
if(vis[now]) return ;
if(fg) fath[now]=fa;
f[now][1]=f[now][0];
for(auto to:vec[now]){
if(to==fa) continue;
// printf("now=%lld to=%lld\n",now,to);
dfs(to,now);
f[now][1]^=f[to][0];
f[now][2]^=f[to][1];
}
// printf("now=%lld %lld %lld %lld\n",now,f[now][0],f[now][1],f[now][2]);
}
signed main(){long long q;
scanf("%lld%lld",&n,&q);
for(long long i=1;i<=n;i++) scanf("%lld",&f[i][0]);
for(long long i=1;i<n;i++){
long long x,y;scanf("%lld%lld",&x,&y);
vec[x].push_back(y),vec[y].push_back(x);
}
fg=1;dfs(1,0);memset(vis,1,sizeof(vis));fg=0;
// printf("\n\nnow begin\n");
long long ans=0;
for(long long i=1;i<=q;i++){
long long x,v;scanf("%lld%lld",&x,&v);
// f[fath[fath[x]]][2]^=f[fath[x]][1];
// f[fath[x]][1]^=f[x][0];
// f[fath[x]][2]^=f[x][0];
f[x][0]=v;
f[0][0]=f[0][1]=f[0][2]=0;
vis[x]=0;dfs(x,fath[x]);vis[x]=1;
f[0][0]=f[0][1]=f[0][2]=0;
vis[fath[x]]=0;dfs(fath[x],fath[fath[x]]);vis[fath[x]]=1;
f[0][0]=f[0][1]=f[0][2]=0;
vis[fath[fath[x]]]=0;dfs(fath[fath[x]],fath[fath[fath[x]]]);vis[fath[fath[x]]]=1;
f[0][0]=f[0][1]=f[0][2]=0;
long long sum=(f[x][2]^f[fath[x]][1])^f[fath[fath[x]]][0];
ans+=(sum*((i*i)%MO))%MO;ans%=MO;
// printf("%lld\n",sum);
// f
}
cout<<(ans%MO+MO)%MO;
return 0;
}
/*
CCCCCCCCCCCCC AAA IIIIIIIIII CCCCCCCCCCCCC AAA IIIIIIIIII AAA
CCC::::::::::::C A:::A I::::::::I CCC::::::::::::C A:::A I::::::::I A:::A
CC:::::::::::::::C A:::::A I::::::::I CC:::::::::::::::C A:::::A I::::::::I A:::::A
C:::::CCCCCCCC::::C A:::::::A II::::::IIC:::::CCCCCCCC::::C A:::::::A II::::::II A:::::::A
C:::::C CCCCCC A:::::::::A I::::I C:::::C CCCCCC A:::::::::A I::::I A:::::::::A
C:::::C A:::::A:::::A I::::IC:::::C A:::::A:::::A I::::I A:::::A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::AAAAAAAAA:::::A I::::IC:::::C A:::::AAAAAAAAA:::::A I::::I A:::::AAAAAAAAA:::::A
C:::::C A:::::::::::::::::::::A I::::IC:::::C A:::::::::::::::::::::A I::::I A:::::::::::::::::::::A
C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I A:::::AAAAAAAAAAAAA:::::A
C:::::CCCCCCCC::::C A:::::A A:::::A II::::::IIC:::::CCCCCCCC::::C A:::::A A:::::A II::::::II A:::::A A:::::A
CC:::::::::::::::C A:::::A A:::::A I::::::::I CC:::::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCC::::::::::::C A:::::A A:::::A I::::::::I CCC::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIII CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIIIAAAAAAA AAAAAAA
*/
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 25748kb
input:
1000 994 780089107 4670366 871010085 73730768 526852049 572589363 885190993 1049357301 450850404 460...
output:
69437761
result:
wrong answer 1st numbers differ - expected: '503748432', found: '69437761'
Test #2:
score: 0
Wrong Answer
time: 5ms
memory: 25748kb
input:
1000 999 26885995 181771373 378079250 245122183 660787775 479226046 575400611 257120086 214404794 48...
output:
986563998
result:
wrong answer 1st numbers differ - expected: '301019013', found: '986563998'
Test #3:
score: 0
Wrong Answer
time: 8ms
memory: 25744kb
input:
1000 994 978408146 31636243 945016735 512129400 92881624 689719983 649699545 964802847 100094796 941...
output:
243525632
result:
wrong answer 1st numbers differ - expected: '250985726', found: '243525632'
Test #4:
score: 0
Time Limit Exceeded
input:
100000 99994 194640838 777315353 114710204 754050649 372592717 210279787 542056883 638262010 7998293...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
100000 100000 458877901 215980825 777376132 863774865 34430451 828397116 94813690 931300514 10548367...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
100000 99991 56406146 757409402 876799234 573444553 883023109 326033134 328116703 623771278 41269529...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
1000000 999998 814298729 663807029 628693441 45635199 148428014 913833778 1034283337 600802841 58045...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
1000000 999993 112899321 425466951 471078924 857561298 449437156 710041336 1033281580 23390934 44420...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
1000000 1000000 273043260 1042513348 30746190 864557483 187812119 562837674 263192174 364182254 3537...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
1000000 999995 83067658 1064735371 623243759 757522311 539363923 924297206 75317137 543750195 822898...
