比赛 |
2024暑假C班集训B |
评测结果 |
AAAAAAATTT |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
70 |
用户昵称 |
袁书杰 |
运行时间 |
7.400 s |
代码语言 |
C++ |
内存使用 |
15.54 MiB |
提交时间 |
2024-07-11 10:05:46 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,s,m,deep[500005],ancester[25][500005],u,v,w[100005],ans,father1[100005];
vector<int> a[500005];
int lca(int x,int y) {
if(deep[x]<deep[y]) {
swap(x,y);
}
for(int i=20; i>=0; i--) {
if(deep[ancester[i][x]]>=deep[y]) {
x=ancester[i][x];
}
}
if(x==y) {
return x;
}
for(int i=20; i>=0; i--) {
if(ancester[i][x]!=ancester[i][y]) {
x=ancester[i][x],y=ancester[i][y];
}
}
return ancester[0][x];
}
void dfs(int u,int father) {
deep[u]=deep[father]+1;
ancester[0][u]=father;
for(int i=1; i<=20; i++) {
ancester[i][u]=ancester[i-1][ancester[i-1][u]];
}
for(int v=0; v<a[u].size(); v++) {
if(a[u][v]==father) {
continue;
}
dfs(a[u][v],u);
}
}
void dfs1(int u,int father) {
father1[u]=father;
deep[u]=deep[father]+1;
for(int v=0; v<a[u].size(); v++) {
if(a[u][v]!=father) {
dfs1(a[u][v],u);
}
}
}
int lca1(int x,int y) {
while(x!=y) {
if(deep[x]>=deep[y]) {
x=father1[x];
} else {
y=father1[y];
}
}
return x;
}
int main() {
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>w[1];
w[1]%=1000000007;
s=1;
for(int i=2; i<=n; i++) {
cin>>u>>w[i];
w[i]%=1000000007;
a[u].push_back(i);
a[i].push_back(u);
}
if(n>=5000) {
dfs1(s,1);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
long long t=w[i]%1000000007;
t*=w[j];
t%=1000000007;
t*=w[lca1(i,j)];
t%=1000000007;
ans+=t;
ans%=1000000007;
}
}
cout<<ans;
return 0;
}
else {
dfs(s,0);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
long long t=w[i]%1000000007;
t*=w[j];
t%=1000000007;
t*=w[lca(i,j)];
t%=1000000007;
ans+=t;
ans%=1000000007;
}
}
cout<<ans;
}
return 0;
}