1 条题解
-
1
#include<cstdio> using namespace std; struct edge { int next; int to; }a[400005]; int edgenum,head[200005],w[200005]; int n,ans,maxx; void add(int u,int v)//加入一条从u到v的边 { a[++edgenum].next=head[u]; a[edgenum].to=v; head[u]=edgenum; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) { int max1=0,max2=0;//最大的两个权值 int t1=0,t2=0;//t1代表和的平方,t2代表平方和 for(int j=head[i];j;j=a[j].next) { if(w[a[j].to]>max1)max2=max1,max1=w[a[j].to]; else if(w[a[j].to]>max2)max2=w[a[j].to]; t1=(t1+w[a[j].to])%10007; t2=(t2+w[a[j].to]*w[a[j].to])%10007; } t1=t1*t1%10007; ans=(ans+t1+10007-t2)%10007; if(maxx<max1*max2)maxx=max1*max2; } printf("%d %d\n",maxx,ans); return 0; }
- 1
信息
- ID
- 352
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 6
- 已通过
- 4
- 上传者