题解 P1351 【联合权值】

Rainy7 · 2019-10-09 22:47:27 · 题解

博客食用传送门

• 分析题目

  1. 无向连通图 G 有 n 个点，n-1 条边。

     很明显，给出的是一个无根树

  2. 由于所有联合权值之和可能很大，输出它时要对10007取余。

     易错点，最大值不用取膜，和才要取膜。

• 分析

  因为他是一个无根树，所以不如先给他确认1为其根节点。

  因为他是一个树，那么对于每个点只要考虑3种情况：父节点的父节点（爷爷），他的子节点的子节点，和他有同一个父亲的任意一点（孙子们）

  然后又可以发现，可以忽略每个点的子节点的子节点的计算 ，相应的，只要把每次算父节点的父节点时的值算上2遍就可以了。

  这里稍微解释一下：（理解的人自动跳过）

  设 x 的父节点的父节点是 y 。

  在算 x 的情况时，要以第一种情况（父节点的父节点） 求一次 w_x*w_y。算 y 的情况时，也要以第二种情况（子节点的子节点） 算一遍 w_y * w_x 。

  所以可以直接忽略第二种情况，把第一种情况的结果乘上 2。

  好了继续。

  这么一分析完，就可以直接跑 dfs 了。

  对于每个点，第一种情况直接算(直接乘法)；第二种情况，直接枚举和自己有同一个父亲的所有点，不断更新答案即可。

• 一点细小的优化（我当时以为不加能过）

  直接dfs直接TLE，还需要一点点优化。

  看刚刚最后的结论，发现每次枚举的点权是可以预处理的。

  设 sum[x] 表示点 x 所有子节点点权和。

  而最大值，对于一个点 x ，也求出他的子节点的最大值和次大值。(因为下一层的最大值的点不能和自己乘)

  然后就可以了。

  如果还有些不理解,可以看看代码。

• 代码

  #include<iostream>
  #include<cstdio>
  #include<cmath>
  using namespace std;
  const int dalao=10007;
  struct edge{
        int v,nx;
  }p[400005];
  int n,ne,f[200005];
  int sum[200005],father[200005],w[200005];
  int data[200005][2],gmax[200005][2];//data记录编号 gmax记录具体值 0最大值 1次大值 
  int maxn,ans;
  void read(int u,int v)
  {   
        p[++ne].v=v;
        p[ne].nx=f[u];
        f[u]=ne;
  }
  void getfather(int x,int fa)
  {   
        father[x]=fa;
        for(int i=f[x];i;i=p[i].nx)
        {   
            if(p[i].v==fa)continue;
            getfather(p[i].v,x);
        }
  }
  int main()
  {   
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {   
            int u,v;
            scanf("%d%d",&u,&v);
            read(u,v);
            read(v,u);
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        sum[0]=w[1];
        getfather(1,0);//确认每个点的父节点 
        for(int i=1;i<=n;i++)//预处理 
            for(int j=f[i];j;j=p[j].nx)
            {   
                if(p[j].v==father[i])continue;
                sum[i]=(sum[i]+w[p[j].v])%dalao;//预处理和
                //预处理最大值和次大值 
                if(w[p[j].v]>gmax[i][0]){gmax[i][0]=w[p[j].v];data[i][0]=p[j].v;}
                else if(w[p[j].v]>gmax[i][1]){gmax[i][1]=w[p[j].v];data[i][1]=p[j].v;}
            }
        for(int x=1;x<=n;x++)
        {   
            if(father[father[x]])//存在父节点的父节点 
                ans=(ans+2*w[x]*w[father[father[x]]])%dalao;
            if(father[father[x]])
                maxn=max(maxn,w[x]*w[father[father[x]]]);
            ans=(ans+w[x]*(sum[father[x]]-w[x]))%dalao;
  
            if(data[father[x]][0]!=x)//最大值不能和自己乘 
                maxn=max(maxn,w[x]*gmax[father[x]][0]);
            else maxn=max(maxn,w[x]*gmax[father[x]][1]);
        }
        printf("%d %d\n",maxn,ans);
        return 0;
  }