竞赛讨论区 > 大佬教教我为啥这玩意儿总是通不过啊
头像
牛客305597101号
发布于 2022-11-29 00:11 湖北
+ 关注

大佬教教我为啥这玩意儿总是通不过啊

#include<stdio.h>

long long jis(long long w[],long long u[],long long v[],int n,int i);

long long max(long long a,long long b);

long long dfs(long long u[],long long v[],int n,int p,int f);

int main()

{

int n;

int i;

scanf("%d",&n);

long long w[n+1],u[n+1],v[n+1];

long long sum=0,num=0;

for(i=1;i<=n;i++)

{

scanf("%lld",&w[i]);

}

for(i=1;i<n;i++)

{

scanf("%lld%lld",&u[i],&v[i]);

}

for(i=1;i<n;i++)

{

sum+=jis(w,u,v,n,i);

//if(sum>=1000000007)sum-=1000000007;

}

sum=sum%1000000007;

printf("%lld",sum);

return 0;

}

long long jis(long long w[],long long u[],long long v[],int n,int i)

{

int j;

long long s1=0,s2=0,d,sum=0;

s1=dfs(u,v,n,i,-1);//起始计算点到1的距离(深度)

for(j=i+1;j<=n;j++)

{

s2=dfs(u,v,n,j,-1);//每一个匹配计算点到1的距离 (深度)

d=max(w[i],w[j]);//两点中质量的最大值

sum+=d*(s1+s2);//这个起始计算点类推下所有可能的相互作用值的和

}

return sum;

}

long long max(long long a,long long b)

{

if(b>=a)a=b;

return a;

}

long long dfs(long long u[],long long v[],int n,int p,int f)

{

int i,j,k,h=1,cnt=0;//定义辅助计算值

long long s[n];//定义缓冲数组

//从节点p点开始寻找节点1

if(p==1)

{

return 0;//若是找到节点1,则返回寻找的次数(在当前函数中为零次)

}

for(i=1;i<n;i++)//遍历所有u和v数组,寻找节点P

{

if(u[i]==p&&v[i]!=f)//且之后式子表示避免走回上一个节点

{

s[h]=v[i];//记录与节点P相连的节点

h++;

}

if(v[i]==p&&u[i]!=f)//且之后式子表示避免走回上一个节点

{

s[h]=u[i];//记录与节点相连的节点

h++;

}

}

h--;//出循环后,把h上多加的一个1减去

if(h==0)//s数组为空表示已无下一级连接的节点

{

return -1;//无节点直接返回-1表示此路不通,把进函数前加的计数给减去

}

for(j=h;j>0;j--)//遍历与节点p相连的所有节点

{

cnt++;//每进入函数一次,表示寻找一次,计数加一

cnt+=dfs(u,v,n,s[j],p);//以与节点p相连的点做新的节点p,做新一轮寻找

if(cnt!=0)break;//若返回值不为0,表示此路已通,因为只有唯一路径,所以跳出循环

}

return cnt;//返回寻找的次数表示深度

}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐