NOIP 提高组 2014 联合权值(图论？？？)

时间：2022-08-18 19:12:26

传送门

https://www.cnblogs.com/violet-acmer/p/9937201.html

题解：

　　相关变量解释：

int n;

int fa[maxn];//fa[i] : i的父亲节点

int w[maxn];//w[i] : i的权值

long long sum[maxn];//sum[i] : i节点的所有儿子节点的权值和

int maxSon1[maxn];//maxSon1[i] : i节点的所有儿子中权值最大值（如果有超过两个儿子）

int maxSon2[maxn];//maxSon2[i] : i节点的所有儿子中权值第二大值（如果有超过两个儿子）

vector<int >G[maxn];//存边

vector<int >son[maxn];//son[i] : 记录节点 i 的所有儿子节点

　　步骤：

　　(1):先Dfs(u,f)预处理出节点u的父亲节点fa[u],儿子节点son[u]，儿子节点的权值和sum[u]，以及儿子节点的权值最大的前两个权值maxSon1[u],maxSon2[u];

　　(2):如果某节点 i 含有两个及以上儿子，则每两个儿子间也可构成长度为 2 的边长，求出节点 i 的儿子节点的联合权值，并判断是否可以更新联合权值的最大值；

　　(3):求 i 节点与其父亲的父亲节点 j 构成的联合权值，并将其二倍(i 与 j 构成联合权值，同样 j 与 i 也可以构成联合权值，所以需要加入两个)与加入到联合权值之和

　　     中，并判断是否可以更新联合权值的最大值。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define pb(x) push_back(x)

 #define mem(a,b) memset(a,b,sizeof(a))

 const int maxn=+;

 const int MOD=;

 int n;

 int fa[maxn];

 int w[maxn];

 long long sum[maxn];

 int maxSon1[maxn];

 int maxSon2[maxn];

 vector<int >G[maxn];

 vector<int >son[maxn];

 void addEdge(int u,int v)

 {

     G[u].pb(v);

     G[v].pb(u);

 }

 void Dfs(int u,int f)

 {

     fa[u]=f;

     for(int i=;i < G[u].size();++i)

     {

         int to=G[u][i];

         if(to != f)

         {

             son[u].pb(to);

             sum[u] += w[to];

             if(w[to] > maxSon1[u])

             {

                 if(maxSon1[u] > maxSon2[u])

                     maxSon2[u]=maxSon1[u];

                 maxSon1[u]=w[to];

             }

             else if(w[to] > maxSon2[u])

                 maxSon2[u]=w[to];

             Dfs(to,u);

         }

     }

 }

 void Solve()

 {

     mem(sum,);

     mem(maxSon1,);

     mem(maxSon2,);

     Dfs(,-);

     int maxRes=;

     int res=;

     for(int i=;i <= n;++i)//步骤(2)

     {

         if(son[i].size() >= )

         {

             maxRes=max(maxRes,maxSon1[i]*maxSon2[i]);

             for(int j=;j < son[i].size();++j)

                 res=res%MOD+((sum[i]-w[son[i][j]])%MOD)*(w[son[i][j]]%MOD);

         }

     }

     for(int i=;i <= n;++i)//步骤(1)

     {

         if(fa[i] != )

         {

             maxRes=max(maxRes,w[fa[fa[i]]]*w[i]);

             res=res%MOD+*w[fa[fa[i]]]*w[i];

         }

     }

     printf("%d %d\n",maxRes,res%MOD);

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         int u,v;

         scanf("%d%d",&u,&v);

         addEdge(u,v);

     }

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

         scanf("%d",w+i);

     Solve();

 }

　　坑：　　

　　　　步骤(2)的情况刚开始忘了，然后，吃了一发wa.................

相关文章