洛谷 题解 P1351 【联合权值】

Problem

P1351 【联合权值】

record

• 用时： 99ms
• 空间： 13068KB(12.76MB)
• 代码长度： 3.96KB
• 提交记录： R9883701
• 注： 使用了
  1. o1 优化
  2. o2 优化
  3. o3 优化
  4. use-v4
  5. 快读快输

Solution

60 or 70 pts

直接爆搜，枚举每两个距离为 2 的点，然后记录答案。

写法优异可以拿走 70 pts , 但是 use-v4 几乎铁定是 60 pts 。

代码。。。就不放了，有兴趣的可以看：

60 pts( use-v4 )

70 pts( use-v3 )

70⇒100 pts

考虑我们的思路慢在哪儿？

在于组合！

考虑一个菊花图，复杂度几乎是 Θ(n^2) 的，当然慢。

想到乘法交换律（数学老师不要怪我这么长时间才想起你）

这时候考虑任意两个距离为 2 的有序点对一定会有一个中间点，枚举这个点即可，并不需要搜索。复杂度 Θ(n)Θ(n) ，菊花图不会卡

100 pts

思路基本没什么问题了吧！

等等，图 G 上联合权值的最大值呢？

每次记录中间点相邻点中最大的和次大的即可。

没问题了吧？

不，还有问题！

答案要乘 2 ！

因为题目可以看成一对有序点对要计算两次。

Code

 // luogu-judger-enable-o2

 /*

     Problem:    P1351 联合权值

     Author:     航空信奥

     Date:       2018/08/18

     Upload:     Luogu

     P.s.:       use-v4

 */

 #pragma GCC optimize("O1")

 #pragma GCC optimize("O2")

 #pragma GCC optimize("O3")

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 using namespace std;

 namespace AuthorName { /* 防重名 */

     template <typename _TpInt> inline _TpInt read();

     template <typename _TpInt> inline void write(_TpInt x);

 #   define Online_Judge

 #   define Max_N

 #   define Mod 

     vector<vector<int> > g;

     int *w;

     int maxx = , sum = ;

     void work(int p)

     {

         int max_1st = , max_2nd = , temp_sum = ;

         for (size_t i = ; i < g[p].size(); i++) {

             if (w[g[p][i]] > max_1st) {

                 max_2nd = max_1st;

                 max_1st = w[g[p][i]];

             }

             else if (w[g[p][i]] > max_2nd) {

                 max_2nd = w[g[p][i]];

             }

             sum = (sum + temp_sum * w[g[p][i]]) % Mod;

             temp_sum = (temp_sum + w[g[p][i]]) % Mod;

         }

         maxx = max(maxx, max_1st * max_2nd);

     } 

     int main()

     {

         int n;

         n = read<int>();

         g.resize(n + );

         w = new int[n + ];

         int u, v;

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

             u = read<int>();

             v = read<int>();

             g[u].push_back(v);

             g[v].push_back(u);

         }

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

             w[i] = read<int>();

         }

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

             work(i);

         }

         write(maxx), putchar(), write((sum << ) % Mod), putchar();

         return ;

     }

 #ifdef Online_Judge

     char BufferRead[ << ];

     int rLen = , rPos = ;

     inline char Getchar()

     {

         if (rPos == rLen) rPos = , rLen = fread(BufferRead, ,  << , stdin);

         if (rPos == rLen) return EOF;

         return BufferRead[rPos++];

     }

 #else

 #   define Getchar() getchar()

 #endif

     template <typename _TpInt>

     inline _TpInt read()

     {

         register int flag = ;

         register char c = Getchar();

         while ((c > '' || c < '') && c != '-')

             c = Getchar();

         if (c == '-') flag = -, c = Getchar();

         register _TpInt init = (c & );

         while ((c = Getchar()) <= '' && c >= '')

             init = (init << ) + (init << ) + (c & );

         return init * flag;

     }

     template <typename _TpInt>

     inline void write(_TpInt x)

     {

         if (x < ) {

             putchar('-');

             write<_TpInt>(~x + );

         }

         else {

             if (x > ) write<_TpInt>(x / );

             putchar(x %  + '');

         }

     }

 }

 int main()

 {

     AuthorName::main();

     return ;

 }