前缀和怎么做...

做出来答案不对啊QAQ

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=200000+5;
vector<int> G[maxn];
int w[maxn];
int main(){
//freopen("link.in","r",stdin);
//freopen("link.out","w",stdout);
int n,u,v,sumans=0,maxans=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n;i++){
if(G[i].size()>=2){
int big1=0,big2=0,sum=0;
for(int j=0;j<G[i].size();j++){
int x=G[i][j];
if(w[x]>big1){
big2=big1;
big1=w[x];
}
else if(w[x]>big2) big2=w[x];
sum=(sum+w[x])%10007;
}
maxans=max(maxans,big1*big2);
for(int j=0;j<G[i].size();j++) sumans=(sumans+w[G[i][j]]*(sum-w[G[i][j]]))%10007;
}
}
printf("%d %d\n",maxans,sumans);
return 0;
}

1 条评论

  • @ 2016-10-14 13:32:16

    好吧是我太弱没注意n-1行输入边QAQ

  • 1

信息

ID
1906
难度
7
分类
图结构 点击显示
标签
递交数
5638
已通过
914
通过率
16%
被复制
9
上传者