比赛 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;
}