联合权值dp
联合权值
洛谷中可找到
题目传送门https://www.luogu.org/problemnew/show/P1351
这题我就得了70分（TLE） GG了
就是遍历它孩子的孩子（爷爷和孙子），然后相乘；
ps：这样会有很多重复，TLE
1 #include<cstdio> 2 #include<iostream> 3 #define maxn 200000+10 4 using namespace std; 5 int max(int x,int y) 6 { 7 return x>y?x:y; 8 } 9 int n; 10 struct ii{ 11 int u,v,nxt; 12 }a[maxn*2]; 13 int w[maxn]; 14 int head[maxn]; 15 int o; 16 inline void add(int x,int y) 17 { 18 a[++o].u=x; 19 a[o].v=y; 20 a[o].nxt=head[x]; 21 head[x]=o; 22 } 23 int main() 24 { 25 // freopen("link.in","r",stdin); 26 // freopen("link".out,"w",stdout); 27 scanf("%d",&n); 28 for(int i=1,x,y;i<n;++i) 29 { 30 scanf("%d%d",&x,&y); 31 add(x,y); 32 add(y,x); 33 } 34 for(int i=1;i<=n;++i) 35 scanf("%d",&w[i]); 36 int jl=0; 37 int zui=0,he=0,wkk=0; 38 for(int i=1;i<=n;++i) 39 { 40 for(int j=head[i];j;j=a[j].nxt) 41 { 42 for(int zz=head[a[j].v];zz;zz=a[zz].nxt) 43 { 44 if(a[zz].v!=i) 45 { 46 wkk=w[a[zz].v]*w[i]; 47 zui=max(zui,wkk); 48 he+=wkk; 49 he%=10007; 50 } 51 } 52 } 53 } 54 printf("%d %d",zui,he); 55 return 0; 56 }
正解
#include<iostream> #include<cstdio> #define maxn 300000+10 using namespace std; int n; int max(int x,int y) { return x>y?x:y; }//手写max，fast struct ii{ int v,nxt; }a[1000000];//链式强向星存图1 int head[300000]; int w[300000]; int he,ma;//ans int o;//存图 void add(int x,int y) { a[++o].v=y; a[o].nxt=head[x]; head[x]=o; } int main() { cin>>n; int x,y; for(int i=1;i<=n-1;++i) { scanf("%d%d",&x,&y);//输入 add(x,y);add(y,x);//正反存一遍 } for(int i=1;i<=n;++i) { scanf("%d",&w[i]);//输入价值 } int sum,zui;//sum是孩子加起来的和，zui是孩子中最大的 for(int i=1;i<=n;++i) { sum=(zui=w[a[head[i]].v])%10007;//初始值 for(int j=a[head[i]].nxt;j;j=a[j].nxt)//从第二个孩子开始遍历 { //这一部分是求和 he=(he+sum*w[a[j].v])%10007;//乘法结合律 sum=(sum+w[a[j].v])%10007;//更新孩子和 //这一部分是求最大值 ma=max(ma,zui*w[a[j].v]);//更新最大值 zui=max(zui,w[a[j].v]);//更新孩子中的最大值 //因为这是最后更新的，所以不用担心出现最大值和自己相乘 } } printf("%d %d",ma,he*2%10007);//别忘了he*2 return 0; }
投递华为等公司10个岗位
