2020-01-13 21:36 博乐科技_服务端开发工程师

关注

NOPI2014联合权值&&洛谷P1351

这一道题，怎么说呢，就是优化优化再优化！！

首先看题目：

题目描述

无向连通图 GG 有 nn 个点，n-1n−1 条边。点从 11 到 nn 依次编号,编号为 ii 的点的权值为 W_iWi，每条边的长度均为 11。图上两点 (u, v)(u,v) 的距离定义为 uu 点到 vv 点的最短距离。对于图 GG 上的点对 (u, v)(u,v)，若它们的距离为 22，则它们之间会产生W_v \times W_uWv×Wu 的联合权值。

请问图 GG 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入输出格式

输入格式：

第一行包含 11 个整数 nn。

接下来 n-1n−1 行,每行包含 22 个用空格隔开的正整数 u,vu,v，表示编号为 uu 和编号为 vv 的点之间有边相连。

最后 11 行,包含 nn 个正整数，每两个正整数之间用一个空格隔开，其中第 ii 个整数表示图 GG 上编号为 ii 的点的权值为 W_iWi。

输出格式：

输出共 11 行,包含 22 个整数，之间用一个空格隔开,依次为图 GG 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对1000710007取余。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

20 74

说明

开始，以往同样的思路分析(接下来是我思考的全过程，并且错的思路也会展示，但希望继续读下去，绝对有帮助呀)

第一步：每一条边的距离都是1，其实就是子节点与父节点的关系是1,我们就思考怎么找到距离为2的点。

第二步：刚开始，什么也没说直接暴力一波，BFS因为BFS有个特点，他可以分层遍历，也就是说他是横向搜索，这刚好满足我们的条件，所以如果以s为起点，走一遍BFS之后，所有的点与他的距离都出来了，那么怎么记录这个距离呢，建立一个dis数组，初始化dis[s]=0，然后dis[u]=dis[u]+1。这样就推出来了。

第三步：考虑能否优化，是可以优化的，因为只要dis[u]==3这个点之后子节点，说明距离为2的都被比较完了(因为BFS为横向搜索)，然后break就可以了，而不用继续去更新剩下点与起点的距离了，所以代码为：

void BFS(int s,int n)
{
    queue<int>q;
    for(int i=1;i<=n;i++)   vis[i]=false;//标记一下，不能回到之前的节点啊！
    q.push(s);vis[s]=true;dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(dis[u]==2)
        {
            ans=max(ans,save[u]*save[s]);
            sum=(sum+save[u]*save[s])%10007;
           // printf("%d %d\n",s,u);
        }
        if(dis[u]==3) break;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int e=edge[i].e;
            if(vis[e]==false)
            {
                dis[e]=dis[u]+1;//距离父节点距离加1
                vis[e]=true;
                q.push(e);
            }
        }
    }

}

好了，我很认真，然后T掉。然后我以为调取队列需要时间（天真），然后就用自己写了一个队列：

void BFS(int s,int n)
{

    for(int i=1;i<=n;i++)   vis[i]=false;
    Q[1]=s;vis[s]=true;dis[s]=0;
    int top=1,cur=1;
    while(top<=cur)
    {
        int u=Q[top];
        top++;
        if(dis[u]==2)
        {
            ans=max(ans,save[u]*save[s]);
            sum=(sum+save[u]*save[s])%10007;
           // printf("%d %d\n",s,u);
        }
        if(dis[u]==3) break;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int e=edge[i].e;
            if(vis[e]==false)
            {
                dis[e]=dis[u]+1;
                vis[e]=true;
                Q[++cur]=e;
            }
        }
    }
}

然后还是T，所以我们的思想绝对对，但不是最优解，而且看了一下实例用时4832MS，这不是用几个优化可以解决的，要解决这个问题除非O（n）。

第四步：再想一下我们纯粹的思路，遍历每一个点，找到与他相邻的孙节点(子节点的子节点)，然后一一比较，其实这就是BFS的思路，BFS优化了一下暴力求解，如果暴力时间会更长。这说明BFS也不可以，所以这个思路就不是最优解。

第五步：我们想一下，对于一个点，还有什么情况可以距离为2，好像没有了，但是(到这里我思路瞬间开窍)，想到一个东西，两点最近公共祖先！！对！两点最近公共祖先启发了我，除了该节点与孙节点距离为2，该节点的任意两个节点距离都是2！！！

第六步：到这里，我们就可以直接遍历每一个点的子节点，然后任意两个子节点的权值相乘，sum加起来，并比较最大值。

第七步：上面的思路复杂度确实接近到了O(n),但是还有一些细节问题，还能不能继续优化！能！因为没次两个点相乘最大值都要比较一次，咱们在这里可以求出与这个节点的子节点权值最大和第二大，他俩的乘积一定是该节点的子节点中任意两点乘积最大值。这样处理也比较好处理，我们只需要访问节点的过程中记录最大和次大，最后乘起来就是该节点下任意两节点的最大值。如何确定最大值与次大值，这个思想想了好久：

        int e=edge[i].e;
        if(save[e]>maxl1)
        {
            maxl2=maxl1;
            maxl1=save[e];
        }
        else if(save[e]>maxl2)
            maxl2=save[e];

这样就确定了最大值和次大值，然后把每一个节点遍历一下，求出节点连接的最大联合权值，最大联合权值get√。

第八步：怎么确定任意该点任意两点的和？好了记录连接的每一个点，遍历暴搜：

for(int i=1;i<=ans;i++)
    for(int k=i+1;k<=ans;k++)
    {
        sum+=save[i]*save[k];
        sum%=10007;
    }

然后依旧超时，因为这样假如一个点的子节点有1000个(不排除可能，因为总点数20000),这仅仅是一个点！！我们就复杂度就到了（1000*999）/2次运算！

第九步：怎么优化现在的求和运算呢？这里有个最基本的思想叫做 乘法结合律（没想到小学这么low的思想有这么大作用）：

我们根据这两个for循环可以看出，先枚举第一个子节点然后与其他每一个节点相乘，再枚举下一个与其他节点相乘。

其实这就是在进行一个过程，假设有 a,b,c,d四个点，枚举过称为：

1.sum+=(a*b+a*c+a*d)

2.sum+=(b*c+b*d)

3.sum+=c*d

4.sum+=d*0

我们看到这里可以提出来呀！！！

1.sum+=a*(b+c+d)

2. sum +=b*(c+d)

3. sum+=c*d

4.sum+=d*0

第十步：通过以上算式，我们可以看出这就减少了不止一次运算啊，而且我们可以在遍历过程中进行计算，我们设置一个变量v=0，表示当前的和，然后当枚举第一个节点的时候 sum+=save[e]*v,然后 v+=save[e]。然后进行第二次枚举sum+=save[e]*v,v+=save[e]，这个时候v变成之前的值，以此类推这样下去就是任意子节点权值乘积的和。如果还不懂，举个例子：

还是四个子节点权值：a,b,c,d

1.sum+=a*0,v=a;

2.sum+=b*a,v=a+b;

3.sum+=c*(a+b),v=a+b+c;

4.sum+=d*(a+b+c),v=a+b+c+d;

发现没有这与上面的式子完全相同不过是倒过来了，这次理解了叭。。

第十一步：那么现在我们就已经把求子节点任意两点权值之和的复杂度优化到了O（M）,M为子节点个数。

第十二步：写一下程序叭，基本就可以写了，但是一定要注意同余模定理的使用，必须要每一步取模！！！！

具体代码+注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
bool vis[maxn];
int dis[maxn];
ll save[maxn];
/*坚持不懈，无懈可击*/
/*中国有句古话，叫做置之死地而后生！*/
ll ans=-INF;
ll sum=0;
struct node{
    int e,next;
}edge[maxn];
ll cnt=0;
int head[maxn];
bool vis1[maxn];
int Q[maxn];
void restart(int n)
{
    for(int i=1;i<=n;i++)
        head[i]=-1;
    cnt=0;
    for(int i=1;i<=n;i++)
        vis[i]=false;
}
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
void solve(int x)
{
    ll maxl1=-1,maxl2=-1;
    ll z=0;ll w=0;
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        int e=edge[i].e;
        if(save[e]>maxl1)//求一下最大值
        {
            maxl2=maxl1;
            maxl1=save[e];
        }
        else if(save[e]>maxl2)
            maxl2=save[e];//求一下次大值
        sum+=save[e]*w;//上文我们阐述的模拟结合律算法。
        w+=save[e];
        w%=10007;
        sum%=10007;
    }
        ans=max(ans,maxl1*maxl2);//比较一下最大值的乘积
}
int main()
{
    int n;
    scanf("%d",&n);
    restart(n);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    for(int i=1;i<=n;i++)
        scanf("%lld",&save[i]);
    for(int i=1;i<=n;i++)
        solve(i);
    printf("%lld %lld\n",ans,(sum*2)%10007);//不要忘记取模！
    return 0;
}

祝大家一次AC！！！