BZOJ 1787 [Ahoi2008]Meet 紧急集合

题目大意

给你一棵树，求出一个点使得其到三个点的距离最短。

这题十分蛇皮……

首先看到这题，一脸懵比，只能先猜结论……会不会和路径有关？我们画出两两点的路径，发现一个事情：如果选择的点不在路径沿途的点上，此时挪近一个点到路径旁，一定会有两个点的距离缩短，一个点的距离增长，总距离是减小的。

在确定完一定在路径上之后，我们发现对于两个点而言如果在这两个点的路径上则结果相等，之后考虑这条路径上哪个点距离第三个点最近。如果这个点不在子树里，那就是LCA。如果在子树里就是它的fa.如果在子树里则不好判断，但可以直接反转这三个点的顺序从而达到变相转为状态1，所以直接求出两两LCA和距离，算一下求最小就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,b,u[4000],f[2][4000],g[2][4000],ans;
int main()
{
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;++i) scanf("%d",u+i);
    memset(f,-1,sizeof f),memset(g,-1,sizeof g);
    f[0][0]=0;
    for(int i=1;i<=n;++i)
    {
        int tmp=i&1;    
        for(int j=0;j<=b;++j)
        {
            f[tmp][j]=max(f[tmp^1][j],g[tmp^1][j]);
            if(j)
            {
                g[tmp][j]=f[tmp^1][j-1];
                if(g[tmp^1][j-1]!=-1) g[tmp][j]=max(g[tmp][j],g[tmp^1][j-1]+u[i]);
            }
        }
    }
    ans=max(f[n&1][b],g[n&1][b]);
    memset(f,-1,sizeof f),memset(g,-1,sizeof g);
    g[1][1]=u[1];
    for(int i=2;i<=n;++i)
    {
        int tmp=i&1;
        for(int j=0;j<=b;++j)
        {
            f[tmp][j]=max(f[tmp^1][j],g[tmp^1][j]);
            if(j)
            {
                g[tmp][j]=f[tmp^1][j-1];
                if(g[tmp^1][j-1]!=-1) g[tmp][j]=max(g[tmp][j],g[tmp^1][j-1]+u[i]);
            }
        }
    }
    ans=max(ans,g[n&1][b]);
    printf("%d\n",ans);
    return 0;
}