UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214250#2763. 幻想乡的拜访naroto2022602256ms1872kbC++1.4kb2024-11-16 20:26:112024-11-16 23:12: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[MN][25],ans;
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];
}
int main(){
    n=read();
    for(int i=1; i<n; i++){
        ll u=read(),v=read();
        add(u,v);add(v,u);
    }
    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;
}

Details

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

Test #1:

score: 10
Accepted
time: 3ms
memory: 1184kb

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: 3ms
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: 3ms
memory: 1180kb

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: 597ms
memory: 1868kb

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: 871ms
memory: 1872kb

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: 779ms
memory: 1864kb

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: 0
Time Limit Exceeded

input:

1000000
984750 990109
970095 984750
996126 970095
998081 990109
987074 970095
962711 970095
916630 9...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000000
947305 936749
948062 947305
970449 947305
988744 948062
998703 988744
986194 947305
997762 9...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

1000000
952012 962256
982471 962256
955412 952012
953636 962256
991390 952012
998704 953636
999294 9...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

1000000
900864 972452
986047 900864
953966 972452
977801 986047
997024 972452
954755 953966
999240 9...

output:


result: