10分WA求助。。。和题解对拍n组数据完全一样。。。

回复帖子

@xiaolou 2018-12-23 10:17 回复
#include <bits/stdc++.h>

using namespace std;
vector <int> dep[200005];
int n;
int b[200005][20];
long long a[200005];
struct Node
{
    int v;
    Node *next;
}*h[200005],pool[400005];
int tot=0;
void adde(int u,int v)
{
    Node *p=&pool[++tot];
    p->v=v;
    p->next=h[u];
    h[u]=p;
}
int d[200005];
int vis[200005];
void dfs(int u)
{
    dep[d[u]].push_back(u);
    vis[u]=1;
    int v;
    for(int i=1;(1<<i)<=d[u];i++)
    {
        b[u][i]=b[b[u][i-1]][i-1];
    }
    for(Node *p=h[u];p;p=p->next)
    {
        if(vis[v=p->v]==0)
        {
            d[v]=d[u]+1;
            b[v][0]=u;
            dfs(v); 
        }
    }
}

int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin >> x >> y;
        adde(x,y);
        adde(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    } 
    d[1]=1;
    dfs(1);
    long long ans=0;
    long long maxans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>2)
        {
            ans=(a[i]*a[b[i][1]]+ans)%10007;
            maxans=max(maxans,a[i]*a[b[i][1]]);
        }
    }
    ans*=2;
    for(int i=1;i<=n;i++)
    {
        int depth=d[i];
        for(int j=0;j<dep[depth].size();j++)
        {
            if(dep[depth][j]!=i)
            {
                ans+=a[dep[depth][j]]*a[i];
                maxans=max(maxans,a[dep[depth][j]]*a[i]);
            }
        }
    }
    cout << maxans << " " << ans%10007;
    return 0;
} 
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。