题解

31 条题解

  • 3
    @ 2015-04-15 21:12:07

    我是弱渣,虽然有大神题解,呵呵,看不懂。于是自己写了。

    首先是最容易想到的。用前向星,邻接表来存图。然后枚举所有产生的点。嗯,时间复杂度会被卡成N^2,然后只能60分

    优化下。比如1和3和3和1,可以提前计算,算1和3的时候乘2.然后3和1就不算了。只要判断i<J再算就可以优化。大概70分。所以这个思路本身就有不能拿到满分。

    仔细分析,考虑这样有个点。A,所有和他相邻的点为B,C,D等等。那么这些点都可以两两产生联合权值。不难推出其中公式。

    拿3个点的情况来举例。A连着B,C,D3个点,记这3个点的W为b,c,d。那么总的权值是bc+bd+cb+cd+db+dc=2bc+2bd+2cd。这是n^2时候的枚举算法。我们处理下。看到这个式子想到什么?没错,完全平方。就是(a+b)^2=a^2+b^2+2ab.

    同理。把这个式子一般化。不难知道。2bc+2bd+2cd=(b+c+d)^2-b^2-c^2-d^2.这样的话,在N的复杂度就能瞬间得到一个顶点答案。因此只要枚举所有点即可。

    至于最大值只要把这个点相邻的点最大值W和次大值W找出来就是该点能出来的最大值。跟max比较。

    这样的话只要枚举所有节点就可以得出答案。时间复杂度只有N,轻松AC。

    附上代码,star代表前向星(自行百度)一种存图方式。

    ###block code
    program P1906;
    const maxn=400001;
    var ans,max,sum2,sum:int64;
    i,j,n,now,k,num1,num2:longint;
    s,w:array[1..200000] of longint;
    first,last:array[1..maxn] of longint;
    data,new:array[1..maxn,1..2] of longint;
    procedure star;//构造计数排序优化的前向星。自己百度百科不谢。
    begin
    for i:=1 to n-1 do
    begin
    read(data[i,1],data[i,2]); inc(s[data[i,1]]);
    data[n-1+i,1]:=data[i,2]; data[n-1+i,2]:=data[i,1]; inc(s[data[i,2]]);
    end;
    first[1]:=1;
    for i:=2 to n do begin first[i]:=first[i-1]+s[i-1]; last[i]:=first[i]-1; end;
    for i:=1 to (n-1) shl 1 do
    begin
    inc(last[data[i,1]]); now:=last[data[i,1]]; new[now,1]:=data[i,1]; new[now,2]:=data[i,2];
    end;

    end;
    begin //main
    fillchar(data,sizeof(data),0); ans:=0; max:=0; fillchar(last,sizeof(last),0);
    fillchar(s,sizeof(s),0); fillchar(first,sizeof(first),0);
    read(n);
    star;
    for i:=1 to n do read(w[i]); //以上是读入

    for i:=1 to n do //枚举所有点
    begin
    sum:=0; num1:=0; num2:=0; sum2:=0;
    //sum表示(a+b+c+....)。sum2是a^2+b^2+.... 自己看上面题解。通过sum和sum2可以得到总的权值
    //num1是该点最大的W,2是次W。
    if s[i]>1 then //1个点出度大于2才能有权值产生。枚举所有出度大于2的点

    begin
    for j:=first[i] to last[i] do //枚举所有跟i节点相邻的点
    begin
    sum:=w[new[j,2]]+sum; sum2:=w[new[j,2]]*w[new[j,2]]+sum2; //计算sum
    if w[new[j,2]]>num2 then //寻找最大值和次大值
    if w[new[j,2]]>num1 then
    begin
    num2:=num1; num1:=w[new[j,2]];
    end
    else
    begin
    num2:=w[new[j,2]];
    end;
    end;
    end;
    ans:=((ans+(sum*sum)-sum2) mod 10007); //ans是最终总答案。该i节点总权值为sum*sum-sum2
    if num1*num2>max then //计算该节点能产生的最大值。如果比max大就保留
    max:=num1*num2;
    end;
    ans:=ans mod 10007; //保险
    write(max,' ',ans); //max最大值。ans总答案、
    end. //完美解决

  • 2
    @ 2017-04-14 13:54:21
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<map>
    #include<cstring>
    #include<vector>
    #define inf 1e9
    #define ll long long
    #define For(i,j,k) for(ll i=j;i<=k;i++)
    #define Dow(i,j,k) for(ll i=k;i>=j;i--)
    using namespace std;
    int v[1000001],poi[1000001],nxt[1000001],f[1000001],cnt,n,ma,ans;
    inline void add(int x,int y)
    {
        poi[++cnt]=y;nxt[cnt]=f[x];f[x]=cnt;
    }
    void doit(int x)
    {
        int sum=0;
        int maxn=0,s_maxn=0;
        for(int i=f[x];i;i=nxt[i])
        {
            int p=poi[i];
            if(v[p]>maxn)   s_maxn=maxn,maxn=v[p];
            else if(v[p]>s_maxn)    s_maxn=v[p];
            ans+=v[p]*sum;
            sum+=v[p];
            ans%=10007;sum%=10007;
        }
        ma=max(ma,maxn*s_maxn);
    }
    int main()
    {
        scanf("%d",&n);
        For(i,1,n-1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);add(y,x);
        }
        For(i,1,n)  scanf("%d",&v[i]);
        For(i,1,n)  doit(i);
        printf("%d %d",ma%10007,ans*2%10007);
    }
    
    • @ 2017-10-16 15:12:21

      dalao
      ,你的ma不用模的,模了就WA了

  • 1
    @ 2017-11-02 13:39:30

    由于前向星好难,本蒟蒻不会写
    所以只能用vector了QAQ
    不一定要开long long也能过的
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <queue>
    #define N 200100
    const int k=10007;
    using namespace std;
    vector<int>a[N];
    int w[N];
    int n,x,y,v,p,q,l,maxn,ans;
    int max1,max2;
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
    int x,y;
    scanf("%d %d",&x,&y);
    a[x].push_back(y);
    a[y].push_back(x);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
    {
    l=a[i].size();
    max1=-1001;
    max2=-1001;
    p=0,q=0;
    if(l>1)
    {
    for(int j=0;j<l;j++)
    {
    v=a[i][j];
    p=(p+w[v])%k;
    q=(q+w[v]*w[v])%k;
    if(w[v]>=max1)
    {
    max2=max1;
    max1=w[v];
    }
    if(w[v]<max1&&w[v]>=max2) max2=w[v];
    }
    ans=(ans+p*p-q)%k;
    maxn=max(maxn,max1*max2);
    }
    }
    printf("%d %d",maxn,ans);
    return 0;

    }

  • 1
    @ 2017-11-02 13:38:03

    注意
    要开long long
    不然只有70分
    经典vector 拒绝bb
    #include <iostream>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #define N 10000000+100
    using namespace std;
    long long n,c[N],w[N],max1=-N,num,r,sum,m1,m2;
    vector<int> flag[200001];
    int main()
    {
    cin>>n;
    for(int i=1;i<n;i++)
    {
    int x,y;
    cin>>x>>y;
    flag[x].push_back(y);
    flag[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int i=1;i<=n;i++)
    {
    sum=0;m1=0,m2=0;

    for(int j=0;j<=flag[i].size()-1;j++)
    {
    sum+=w[flag[i][j]];
    int x=w[flag[i][j]];
    if(x>m1){m2=m1;m1=x;}
    else
    {
    if(x>m2)m2=x;
    }
    }
    for(int j=0;j<=flag[i].size()-1;j++)
    num=(num+(sum-w[flag[i][j]])*w[flag[i][j]])%10007;
    max1=max(max1,m1*m2);
    }
    cout<<max1<<" "<<num;
    return 0;
    }

  • 1
    @ 2017-10-16 15:31:23
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #define LL long long
    using namespace std;
    template <class _T> inline void read(_T &_x){
        int _t;bool _flag=0;
        while((_t=getchar())!='-'&&(_t>'9'||_t<'0'));
        if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
        while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
        if(_flag)_x=-_x;
    }
    const int maxn=2e5+5;
    const int MOD=10007;
    int n,x,y,head[maxn],du[maxn],cnt;
    LL w[maxn],ans1,ans2;
    struct edge{
        int v,nxt;
    }d[maxn<<1];
    inline void add(int a,int b){
        d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
        d[++cnt].v=a;d[cnt].nxt=head[b];head[b]=cnt;
    }
    
    
    int main(){
        read(n);
        for(int i=1;i<n;++i){
            read(x),read(y);
            add(x,y);du[x]++;du[y]++;
        }
        for(int i=1;i<=n;++i){
            read(w[i]);
        }
        for(int i=1;i<=n;++i){
            if(du[i]<=1)continue;
            LL s1=0,s2=0,w1=0,w2=0;
            for(int k=head[i];k;k=d[k].nxt){
                int v=d[k].v;
                if(w1<w[v])w2=w1,w1=w[v];
                else if(w2<w[v])w2=w[v];
                s1+=w[v];s2+=w[v]*w[v];
                s1%=MOD;s2%=MOD;
            }
            ans1=max(ans1,w1*w2);
            ans2+=(s1*s1%MOD-s2+MOD)%MOD;ans2%=MOD;
        }
        printf("%lld %lld",ans1,ans2);
        
        return 0;
    }
    
  • 1
    @ 2017-09-02 10:40:34

    加一些小技巧。
    #include <iostream>
    using namespace std;
    #include <queue>
    #include <vector>
    #include <algorithm>

    #define INF 99999999
    int val[200010];
    int vis[200010]={0};
    int dis[200010]={INF};
    long long sum=0;
    long long max1=0;
    vector<int> G[200010];
    long long s[200100]={0};
    #include <cstdio>
    int main(){

    int n;
    cin>>n;
    for(int i=1;i<n;i++){
    int from,to;
    scanf("%d%d",&from,&to);
    G[from].push_back(to);
    G[to].push_back(from);
    }
    for(int i=1;i<=n;i++) cin>>val[i];
    //bfs
    long long maxa,maxb;

    for(int i=1;i<=n;i++){
    maxa=maxb=0;
    for(int j=0;j<G[i].size();j++){
    int v=G[i][j];
    s[i]+=val[v];
    if(val[v]>maxa) maxb=maxa,maxa=val[v];
    else if(val[v]>maxb) maxb=val[v];
    max1=max(max1,maxa*maxb);

    }
    for(int j=0;j<G[i].size();j++){
    int v=G[i][j];
    sum+=val[v]*(s[i]-val[v]);
    sum%=10007;
    }

    }
    cout<<max1<<" "<<sum%10007<<endl;
    return 0;
    }

  • 0
    @ 2018-08-31 17:02:19
    #include <cstdio>
    #include <vector>
    
    using namespace std;
    
    int n;
    const int MOD = 10007;
    
    vector<int> tree[200001];
    
    int w[200001];
    
    bool marked[200001];
    vector<int> conn[200001];
    
    long long f[200001];
    int g[200001];
    
    long long csum[200001];
    long long ssum[200001];
    
    int cmax[200001];
    int csecond[200001];
    
    void mk_tree(int node)
    {
        marked[node] = true;
        for (int i = 0; i < conn[node].size(); i++) {
            if (!marked[conn[node][i]]) {
                tree[node].push_back(conn[node][i]);
                mk_tree(conn[node][i]);
            }
        }
    }
    
    void prepare(int node)
    {
        for (int i = 0; i < tree[node].size(); i++) {
            int child = tree[node][i];
            csum[node] = (csum[node] + w[child]);
            ssum[node] = (ssum[node] + w[child]*w[child]);
            if (w[child] > cmax[node]) {
                csecond[node] = cmax[node];
                cmax[node] = w[child];
            } else if (w[child] > csecond[node]) {
                csecond[node] = w[child];
            }
            prepare(child);
        }
    }
    
    void calc(int node)
    {
        for (int i = 0; i < tree[node].size(); i++) {
            int child = tree[node][i];
            calc(child);
            f[node] += f[child];
            g[node] = max(g[node], g[child]);
            f[node] += csum[child] * w[node];
            g[node] = max(g[node], cmax[child]*w[node]);
        }
        f[node] += (csum[node]*csum[node]-ssum[node])/2;
        g[node] = max(g[node], cmax[node]*csecond[node]);
    }
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            conn[u].push_back(v);
            conn[v].push_back(u);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", w + i);
        }
        mk_tree(1);
        prepare(1);
        calc(1);
        printf("%d %d", g[1], (2*f[1])%MOD);
        return 0;
    }
    
  • 0
    @ 2017-10-25 15:01:47

    先在洛谷做的,但洛谷的数据似乎有问题,出现了权值为负的点
    直接交到vijos上就过了
    思路是枚举中间点,前缀和求乘积
    整张图并不需要刻意储存(如果不是这个诡异的输入顺序的话)

    #include<iostream>
    using namespace std;
    long long dp[200010],quan[200010],maxn[200010],minn[200010],qian[200010],hou[200010];
    int main()
    {
        int n,i,a,b;
        long long sum=0,ans=0;
        cin>>n;
        for(i=1;i<n;i++)
         cin>>qian[i]>>hou[i];
        for(i=1;i<=n;i++)
         cin>>quan[i];
        for(i=1;i<n;i++)
        {
            a=qian[i];
            b=hou[i];
            if(quan[a]>=maxn[b])
            {
                minn[b]=maxn[b];
                maxn[b]=quan[a];
            }
            else
            {
                if(quan[a]>minn[b])
                 minn[b]=quan[a];
            }   
            if(quan[b]>=maxn[a])
            {
                minn[a]=maxn[a];
                maxn[a]=quan[b];
            }
            else
            {
                if(quan[b]>minn[a])
                 minn[a]=quan[b];
            }
            sum+=2*dp[a]*quan[b];
            sum+=2*dp[b]*quan[a];
            dp[a]+=quan[b];
            dp[b]+=quan[a];
            sum%=10007;
        }
        for(i=1;i<=n;i++)
        {
            ans=max(ans,maxn[i]*minn[i]);
        }
        cout<<ans<<" "<<sum;
        return 0;
    } 
    
  • 0
    @ 2016-11-12 19:17:35

    中间量一定要用long long,经zjy提醒,输出用I64d,再次鸣谢zjy神犇!!!!
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=400005;
    const int P=1e4+7;
    long long w[MAXN],ans=0,maxn=0;
    int n,a[MAXN],head[MAXN],Next[MAXN],tot=0;
    void addedge(int u,int v)
    {
    a[++tot]=v;Next[tot]=head[u];head[u]=tot;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
    int u,v;scanf("%d%d",&u,&v);
    addedge(u,v);addedge(v,u);
    }
    for(int i=1;i<=n;i++){
    scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;i++){
    long long sum=0;
    int ji=0;
    for(int j=head[i];j;j=Next[j]){
    sum+=w[a[j]];++ji;
    }
    long long tmp=0;
    for(int j=head[i];j;j=Next[j]){
    tmp+=(sum-w[a[j]])*w[a[j]];
    }
    ans+=tmp;ans%=P;
    if(ji>=2){
    long long fir=0,sec=0;
    for(int j=head[i];j;j=Next[j]){
    if(w[a[j]]>fir)sec=fir,fir=w[a[j]];
    else if(w[a[j]]>sec)sec=w[a[j]];
    }
    if(fir*sec>maxn)maxn=fir*sec;
    }
    }
    printf("%I64d %I64d\n",maxn,ans);
    }

  • 0
    @ 2016-10-08 23:28:59

    #include <iostream>
    #include <cstring>
    #include <stdio.h>
    using namespace std;

    long long s[210000];
    long long a[210000];
    long long u[210000],v[210000];
    long long max1[210000],max2[210000];
    long long sum=0,maxi=0;

    void bian(long long &x,long long &a,long long &b){
    if(x>a){
    b=a;
    a=x;
    }
    else
    if (x>b) b=x;
    }

    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<n;++i){
    scanf("%lld %lld",&u[i],&v[i]);

    }
    for(int i=1;i<=n;++i){
    cin>>a[i];

    }
    for(int i=1;i<n;++i){
    long long u1=u[i];
    long long v1=v[i];
    s[u1]+=a[v1];
    s[v1]+=a[u1];
    bian(a[v1],max1[u1],max2[u1]);
    bian(a[u1],max1[v1],max2[v1]);
    }
    for(int i=1;i<=n;++i){
    if(max1[i]*max2[i]>maxi)
    maxi=max1[i]*max2[i];
    }
    for(int i=1;i<n;++i){
    long long u1=u[i];
    long long v1=v[i];
    sum=(sum+(s[u1]-a[v1])*a[v1]%10007)%10007;
    sum=(sum+(s[v1]-a[u1])*a[u1]%10007)%10007;

    }
    cout<<maxi<<' '<<sum<<endl;
    }

  • 0
    @ 2016-09-22 21:24:58

    uses math;
    var
    b,e,d,f,g,fa:array [0..200005] of longint;
    c:array [0..200005,1..2] of longint;
    n,i,j,ans,x,y,t,p:longint;
    procedure findmax(x:longint);
    var i,p:longint;
    begin
    p:=d[x];
    while (p<>0) do begin
    findmax(p);
    c[x,1]:=max(c[x,1],b[p]);
    c[x,2]:=max(c[x,2],c[p,1]);
    p:=g[p];
    end;
    end;
    procedure findsum(x:longint);
    var i,p:longint;
    begin
    p:=d[x];
    while (p<>0) do begin
    findsum(p);
    c[x,1]:=(c[x,1]+b[p]) mod 10007;
    c[x,2]:=(c[x,2]+c[p,1]) mod 10007;
    p:=g[p];
    end;
    end;
    begin
    read(n);
    for i:=1 to n-1 do
    begin
    read(x,y);
    if (x=i+1) then begin t:=x; x:=y; y:=t; end;
    if (d[x]=0) then begin d[x]:=y; f[x]:=y; end else begin g[f[x]]:=y; f[x]:=y; end;
    fa[y]:=x;
    end;
    for i:=1 to n do read(b[i]);
    findmax(1);
    ans:=0;
    for i:=1 to n do
    begin
    t:=c[i,2];
    if (i<>1) then
    if (b[i]<>c[fa[i],1]) then t:=max(t,c[fa[i],1])
    else begin
    x:=fa[i];
    p:=d[x];
    while (p<>0) do begin
    if (p<>i) then t:=max(t,b[p]);
    p:=g[p];
    end;
    end;
    if (i<>1) and (fa[i]<>1) then t:=max(t,b[fa[fa[i]]]);
    ans:=max(ans,t*b[i]);
    end;
    write(ans,' ');
    fillchar(c,sizeof(c),0);
    findsum(1);
    ans:=0;
    for i:=1 to n do
    begin
    t:=c[i,2];
    if (i<>1) then t:=(t+c[fa[i],1]-b[i]+10007) mod 10007;
    if (i<>1) and (fa[i]<>1) then t:=(t+b[fa[fa[i]]]) mod 10007;
    ans:=(ans+t*b[i]) mod 10007;
    end;
    write(ans);
    end.

  • 0
    @ 2016-09-01 21:24:04

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n;
    long long x,y,ans1,ans2;
    long long b[200001],s[200001],max1[200001],max2[200001];
    struct ljh
    {
    long long u,v;
    }a[200001];

    void make(long long &x,long long &a,long long &b)
    {
    if(x>a)
    {
    b=a;
    a=x;
    }
    else if(x>b)b=x;
    }

    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<n;i++)cin>>a[i].u>>a[i].v;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<n;i++)
    {
    x=a[i].u;y=a[i].v;
    //遍历每条边连接的每个结点
    s[x]+=b[y];//以x为起点的,加上新增的一个点的权值
    s[y]+=b[x];//同理
    make(b[y],max1[x],max2[x]);//更新以x为起点的最大权值与次大权值
    make(b[x],max1[y],max2[y]);//同上
    }
    for(int i=1;i<=n;i++)
    if(max1[i]*max2[i]>ans1)ans1=max1[i]*max2[i];
    //计算出最大的联合权值,max1数组表示最大的与i相连的权值,max2数组
    //表示次大的与i相连的数组,既然都与i相连,那么就肯定会两点之间的距离为2
    for(int i=1;i<n;i++)
    {
    x=a[i].u;y=a[i].v;
    ans2=(ans2+((s[x]-b[y])*b[y])%10007)%10007;
    //所有与x点相连的点(除y外)的权值乘y点的权值
    //因为都与x相连相连那么两点间距离肯定为2
    ans2=(ans2+((s[y]-b[x])*b[x])%10007)%10007;
    }
    cout<<ans1<<" "<<ans2;
    return 0;
    }

  • 0
    @ 2016-07-21 15:53:07

    为什么一个点周围的所有权值加起来会超过int,不应该是2000000000,离int上限还差1亿

  • 0
    @ 2016-07-04 18:51:10
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int n,w[200005],s[200005],m[200005];
    struct edge{int a;int b;}e[200005];
    int main(){
        //freopen("input.txt","r",stdin);
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)scanf("%d%d",&e[i].a,&e[i].b);
        for(int i=1;i<=n;i++)scanf("%d",&w[i]);
        for(int i=0;i<n-1;i++){
            int &x=e[i].a,&y=e[i].b;
            s[x]+=w[y],s[y]+=w[x];
            if(w[m[x]]<w[y])m[x]=y;
            if(w[m[y]]<w[x])m[y]=x;
        }
        for(int i=0;i<n-1;i++){
            int &x=e[i].a,&y=e[i].b;
            if(m[y]!=x&&w[x]*w[m[y]]>m[0])m[0]=w[x]*w[m[y]];
            if(m[x]!=y&&w[y]*w[m[x]]>m[0])m[0]=w[y]*w[m[x]];
            int u=(w[x]%10007)*((s[y]-w[x])%10007)%10007,v=(w[y]%10007)*((s[x]-w[y])%10007)%10007;
            if(u<0||v<0)
                printf(" ");
            s[0]=(s[0]+u+v)%10007;
        }
        printf("%d %d\n",m[0],s[0]);
        return 0;
    }
    
    • @ 2016-07-14 21:00:11

      请问可以大概解释一下你的算法么

  • 0
    @ 2016-05-25 19:54:23

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 12228 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

    测试数据 #6: Accepted, time = 31 ms, mem = 12232 KiB, score = 10

    测试数据 #7: Accepted, time = 109 ms, mem = 12224 KiB, score = 10

    测试数据 #8: Accepted, time = 218 ms, mem = 12228 KiB, score = 10

    测试数据 #9: Accepted, time = 218 ms, mem = 12228 KiB, score = 10

    Accepted, time = 576 ms, mem = 12232 KiB, score = 100

    代码
    #include<stdio.h>
    int count=0,max=0,point=0;
    struct node
    {
    int v;int l;
    }s[600050];
    long long int tail=0;
    int w[600050]={0};
    long long int f[600050]={0};
    void add(int u,int v )
    {
    point++;
    s[point].v=v;
    s[point].l=f[u];
    f[u]=point;
    }
    int main()
    {
    int i,j,n,u,v;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    f[i]=-1;
    for(i=1;i<n;i++)
    {
    scanf("%d%d",&u,&v);
    add(u,v);add(v,u);
    }
    for(i=1;i<=n;i++)
    scanf("%d",&w[i]);
    for(i=1;i<=n;i++)
    {
    int sum=0,sum1=0,max1=0,max2=0;
    for(j=f[i];j!=-1;j=s[j].l)/*perfect*/
    {
    tail=w[s[j].v];
    sum=(sum+tail)%10007;
    sum1=(tail*tail+sum1)%10007;
    if(tail>max1)
    {
    max2=max1;max1=tail;
    }
    else
    if(tail>max2) max2=tail;
    }
    sum=sum*sum;
    if(max2!=0) count=(count+sum-sum1)%10007;
    if(max1*max2>max&&max2!=0) max=max1*max2;
    }

    printf("%d %d",max,count);
    return 0;
    }

  • 0
    @ 2015-10-30 20:27:37

    var w,c:array[1..300000] of longint;
    next,head,too:array[1..800000] of longint;
    i,j:longint;
    k,n,m,ans,max1,max2,u,v,s1,s2,p,s:int64;
    begin
    readln(n);
    for i:=1 to n-1 do
    begin
    readln(u,v);
    inc(c[u]);inc(c[v]);
    inc(m);
    too[m]:=v;
    next[m]:=head[u];
    head[u]:=m;
    inc(m);
    too[m]:=u;
    next[m]:=head[v];
    head[v]:=m;
    end;
    for i:=1 to n do read(w[i]);
    for i:=1 to n do
    if c[i]>1 then
    begin
    max1:=0;max2:=0;s1:=0;s2:=0;
    p:=head[i];
    while p<>0 do
    begin
    if w[too[p]]>max1 then begin max2:=max1;max1:=w[too[p]];end
    else if w[too[p]]>max2 then max2:=w[too[p]];
    s1:=s1+w[too[p]];s2:=s2+w[too[p]]*w[too[p]];
    p:=next[p];
    end;
    s:=(s+s1*s1-s2)mod 10007;
    if max1*max2>ans then ans:=max1*max2;
    end;
    s:=s mod 10007;
    writeln(ans,' ',s);
    end.

  • 0
    @ 2015-10-04 16:14:30

    //注意数据,我开int错3个点,开long long就过了
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>

    using namespace std;

    struct Node
    {
    long long nextnode, val, sum;
    long long first, second;
    Node *next;
    } pool[2000005], *N[200005];

    int n, cnt;
    int x[200005], y[200005];

    int main(int argc, const char *argv[])
    {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
    scanf("%d %d", &x[i], &y[i]);
    Node *p = &pool[++cnt];
    p->nextnode = y[i];
    p->next = N[x[i]];
    N[x[i]] = p;
    p = &pool[++cnt];
    p->nextnode = x[i];
    p->next = N[y[i]];
    N[y[i]] = p;
    }
    for (int i = 1; i <= n; ++i)
    scanf("%d", &N[i]->val);
    for (int i = 1; i < n; ++i)
    {
    N[x[i]]->sum += N[y[i]]->val;
    N[y[i]]->sum += N[x[i]]->val;
    if (N[y[i]]->val >= N[x[i]]->first)
    {
    N[x[i]]->second = N[x[i]]->first;
    N[x[i]]->first = N[y[i]]->val;
    }
    else
    {
    if (N[y[i]]->val > N[x[i]]->second)
    N[x[i]]->second = N[y[i]]->val;
    }
    if (N[x[i]]->val >= N[y[i]]->first)
    {
    N[y[i]]->second = N[y[i]]->first;
    N[y[i]]->first = N[x[i]]->val;
    }
    else
    {
    if (N[x[i]]->val > N[y[i]]->second)
    N[y[i]]->second = N[x[i]]->val;
    }

    }
    long long ans1, ans2;
    ans1 = ans2 = 0;
    for (int i = 1; i <= n; ++i)
    {
    if (N[i]->first * N[i]->second > ans1)
    ans1 = N[i]->first * N[i]->second;
    for (Node *p = N[i]; p; p = p->next)
    {
    ans2 += N[p->nextnode]->val * (N[i]->sum - N[p->nextnode]->val);
    ans2 %= 10007;
    }
    }
    printf("%d %d\n", (int)(ans1), (int)(ans2));
    return 0;
    }

  • 0
    @ 2015-09-18 21:23:09

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>

    using namespace std;

    struct Node
    {
    int nextNode;
    Node *next;
    } *p[200005], pool[200005];

    int n, pool_count;
    int length[200005];
    int s[200005], t[200005], u[200005];
    int s1[200005], t1[200005], u1[200005];
    int first[200005], second[200005];

    void dfs(int node)
    {
    for (Node *i = p[node]; i; i = i->next)
    {
    dfs(i->nextNode);
    s[node] += length[i->nextNode];
    s1[node] = max(s1[node], length[i->nextNode]);
    t[node] += s[i->nextNode];
    t1[node] = max(t1[node], s1[i->nextNode]);
    s[node] %= 10007;
    t[node] %= 10007;
    }
    for (Node *i = p[node]; i; i = i->next)
    {
    u[node] += length[i->nextNode] * (s[node] - length[i->nextNode]);
    u[node] %= 10007;
    }
    for (Node *i = p[node]; i; i = i->next)
    {
    if (length[i->nextNode] >= first[node])
    {
    second[node] = first[node];
    first[node] = length[i->nextNode];
    }
    if (length[i->nextNode] < first[node] && length[i->nextNode] > second[node])
    {
    second[node] = length[i->nextNode];
    }
    }
    }
    int main(int argc, const char *argv[])
    {
    scanf("%d", &n);
    int x, y;
    for (int i = 1; i < n; ++i)
    {
    scanf("%d %d", &x, &y);
    if (x > y)
    swap(x, y);
    Node *d = &pool[pool_count++];
    d->nextNode = y;
    d->next = p[x];
    p[x] = d;
    }
    for (int i = 1; i <= n; ++i)
    {
    scanf("%d", &x);
    length[i] = x;
    }
    dfs(1);
    int ans1, ans2;
    ans1 = ans2 = 0;
    int temp;
    for (int i = 1; i <= n; ++i)
    {
    //printf("%d s:%d t:%d u:%d t1:%d\n", i, s[i], t[i], u[i], t1[i]);
    ans2 += (t[i] * length[i] * 2 + u[i]);
    temp = length[i] * t1[i];
    if (temp > ans1)
    ans1 = temp;
    temp = first[i] * second[i];
    if (temp > ans1)
    ans1 = temp;
    ans2 %= 10007;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
    }

  • 0
    @ 2015-09-14 18:07:19

    其实题解很简单,答案1扫一遍图找**最大次大值**就好,答案2用一个**加法结合律**就好。贴个代码,就不要喷这**压行**习惯了。

    #include<stdio.h>
    #define mod 10007
    #define max(a,b) (a>b?a:b)
    long long ans1;int i,j,k,ans2,w[200001],n,s[200001],p1[200001],p2[200001],u[200000],v[200000];

    int main(){
    scanf("%d",&n);
    for(i=0;i<n-1;++i)
    scanf("%d%d",u+i,v+i);
    for(i=1;i<=n;++i){
    scanf("%d",w+i);w[i]%=mod;
    }
    for(i=0;i<n-1;++i){
    s[u[i]]=(s[u[i]]+w[v[i]])%mod;s[v[i]]=(s[v[i]]+w[u[i]])%mod;
    if(w[v[i]]>p1[u[i]]){p2[u[i]]=p1[u[i]];p1[u[i]]=w[v[i]];}
    else if(w[v[i]]>p2[u[i]])p2[u[i]]=w[v[i]];
    if(w[u[i]]>p1[v[i]]){p2[v[i]]=p1[v[i]];p1[v[i]]=w[u[i]];}
    else if(w[u[i]]>p2[v[i]])p2[v[i]]=w[u[i]];
    }
    for(i=0;i<n-1;++i)
    ans2=(ans2+(s[v[i]]-w[u[i]])*w[u[i]]%mod+(s[u[i]]-w[v[i]])*w[v[i]]%mod)%mod;
    for(i=1;i<=n;++i) ans1=max(ans1,p1[i]*p2[i]);
    printf("%lld %d\n",ans1,ans2);
    return 0;
    }

    • @ 2015-09-14 18:08:58

      据说这是**结果**,但是有好多***Warning***
      foo.c: In function 'main':
      foo.c:35:2: warning: unknown conversion type character 'l' in format [-Wformat=]
      printf("%lld %d\n",ans1,ans2);
      ^
      foo.c:35:2: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
      foo.c:35:2: warning: too many arguments for format [-Wformat-extra-args]
      foo.c:9:10: warning: unused variable 'k' [-Wunused-variable]
      int i,j,k;
      ^
      foo.c:9:8: warning: unused variable 'j' [-Wunused-variable]
      int i,j,k;
      ^
      测试数据 #0: Accepted, time = 2 ms, mem = 5168 KiB, score = 10

      测试数据 #1: Accepted, time = 1 ms, mem = 5172 KiB, score = 10

      测试数据 #2: Accepted, time = 0 ms, mem = 5176 KiB, score = 10

      测试数据 #3: Accepted, time = 15 ms, mem = 5172 KiB, score = 10

      测试数据 #4: Accepted, time = 0 ms, mem = 5172 KiB, score = 10

      测试数据 #5: Accepted, time = 0 ms, mem = 5168 KiB, score = 10

      测试数据 #6: Accepted, time = 46 ms, mem = 5172 KiB, score = 10

      测试数据 #7: Accepted, time = 109 ms, mem = 5172 KiB, score = 10

      测试数据 #8: Accepted, time = 187 ms, mem = 5172 KiB, score = 10

      测试数据 #9: Accepted, time = 187 ms, mem = 5172 KiB, score = 10

      Accepted, time = 547 ms, mem = 5176 KiB, score = 100

信息

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