ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214263 | #2763. 幻想乡的拜访 | naroto2022 | 100 | 1042ms | 52296kb | C++ | 1.6kb | 2024-11-16 21:15:49 | 2024-11-16 23:13:23 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define rt 1
using namespace std;
const int MN=1e6+5;
const int mod=1e9+7;
ll n,head[MN],tot,deep[MN],fa[3005][25],ans,s,sz[MN];
struct edge{ll to,nxt;}e[MN<<2];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void add(ll u, ll v){e[++tot].nxt=head[u];head[u]=tot;e[tot].to=v;}
void lca_dfs(ll u, ll f){deep[u]=deep[f]+1;fa[u][0]=f;for(int i=1; i<25; i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=head[u]; i; i=e[i].nxt){ll v=e[i].to;if(v==f) continue;lca_dfs(v,u);}}
ll lca(ll x, ll y){if(deep[x]<deep[y]) swap(x,y);for(int i=24; i>=0; i--) if(deep[x]-(1<<i)>=deep[y]) x=fa[x][i];if(x==y) return x;for(int i=24; i>=0; i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0];}
void dfs(ll u, ll f){
sz[u]=u;
for(int i=head[u]; i; i=e[i].nxt){
ll v=e[i].to;
if(v==f) continue;
dfs(v,u);
sz[u]=(sz[u]+sz[v])%mod;
}
ans=(ans+sz[u]*((s-sz[u]+mod)%mod)%mod)%mod;
}
int main(){
n=read();s=n*(n+1)/2;
for(int i=1; i<n; i++){ll u=read(),v=read();add(u,v);add(v,u);}
if(n<=200){lca_dfs(rt,0);for(int i=1; i<n; i++) for(int j=i+1; j<=n; j++) ans=(ans+i*j%mod*(deep[i]+deep[j]-2*deep[lca(i,j)])%mod)%mod;write(ans);putchar('\n');return 0;}
dfs(rt,0);write(ans);putchar('\n');
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1188kb
input:
200 20 160 90 160 5 90 78 90 186 90 149 90 104 78 136 160 106 78 100 106 168 90 30 5 85 136 28 149 1...
output:
104425891
result:
ok single line: '104425891'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1184kb
input:
200 49 91 20 91 147 91 131 20 36 131 9 131 51 147 173 51 32 36 169 51 180 51 2 91 133 2 72 20 14 169...
output:
145567217
result:
ok single line: '145567217'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1188kb
input:
200 44 72 187 72 115 72 124 115 80 124 34 72 22 115 162 34 123 44 93 22 135 80 5 124 112 72 76 187 3...
output:
226420652
result:
ok single line: '226420652'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1276kb
input:
3000 940 1649 220 1649 1438 1649 2264 1649 1467 940 1825 220 1646 940 571 220 1419 220 2509 1438 264...
output:
781596579
result:
ok single line: '781596579'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1284kb
input:
3000 2156 216 2422 2156 2801 216 2504 2156 2701 2156 2582 2801 1558 2156 864 2582 737 864 2919 1558 ...
output:
236427659
result:
ok single line: '236427659'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1280kb
input:
3000 2966 2885 2657 2885 2613 2966 1686 2613 2803 2885 191 2657 2824 2657 675 2657 2693 191 2798 191...
output:
688220644
result:
ok single line: '688220644'
Test #7:
score: 10
Accepted
time: 219ms
memory: 52276kb
input:
1000000 984750 990109 970095 984750 996126 970095 998081 990109 987074 970095 962711 970095 916630 9...
output:
192557796
result:
ok single line: '192557796'
Test #8:
score: 10
Accepted
time: 250ms
memory: 52160kb
input:
1000000 947305 936749 948062 947305 970449 947305 988744 948062 998703 988744 986194 947305 997762 9...
output:
160385007
result:
ok single line: '160385007'
Test #9:
score: 10
Accepted
time: 312ms
memory: 52296kb
input:
1000000 952012 962256 982471 962256 955412 952012 953636 962256 991390 952012 998704 953636 999294 9...
output:
308556344
result:
ok single line: '308556344'
Test #10:
score: 10
Accepted
time: 261ms
memory: 52264kb
input:
1000000 900864 972452 986047 900864 953966 972452 977801 986047 997024 972452 954755 953966 999240 9...
output:
201471911
result:
ok single line: '201471911'