柒葉灬 的博客

柒葉灬 的博客

题解 P1099 【树网的核】

posted on 2018-08-21 09:50:14 | under 题解 |

思路:在直径上尺取,计算每条路径的偏心距.

  • 方法1:可以选开始的一条,直接暴力计算每个点到这条点的贡献,之后进行递推,可以发现,只要两端点的改变会使得子树每个节点变化,用什么数据结构可以支持(在线修改+查询最大值)呢?——线段树!!!代码就不出示了......100多行,反正也没人看。

  • 方法2:可以证明一条路径的2个端点最长距离是到直径两个端点,可以用反证法证明,所以只要处理非直径上其他点的贡献即可,预处理。

    整理发现,在一个线段上尺取,每一个点有一个贡献,问这些点中最大值是多少?在与两端点贡献比较,单调队列√


    然而我们探索并没有结束,我们仔细观察,我们找的最小值肯定要么是两端点到直径端点的贡献,要么是直径上的点的贡献,那么能不能直接取最小呢?答案是可以,可以证明一条路径上,其他点的贡献<两端点到直径端点的贡献(用反证法可以证明)。


    比如说染色的是直径,红色的是选的路径,显然,绿色点的贡献都小于路径俩端点的贡献,证明over!


即就算加上其他点的贡献,对这条路径的答案也不会有一点影响,所以单调队列就可以去掉了直接取max就行了。

#include<cstdio>
#include<algorithm>
#define M 500005
using namespace std;
int n,m,x,y,z,k,id,top,ans=2e9;
int dis[M],fa[M],head[M];
bool mark[M];
struct edge{
    int to,w,nxt;
}E[M<<1];
void add(int u,int v,int w){
    E[++id]=((edge){v,w,head[u]});
    head[u]=id;//存图
}
void dfs(int f,int x){
    fa[x]=f;
    if(dis[x]>dis[k])k=x;
    for(int i=head[x];i;i=E[i].nxt){
        int y=E[i].to;
        if(y==f||mark[y])continue;
        dis[y]=dis[x]+E[i].w;
        dfs(x,y);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    dis[1]=1,dfs(0,1);
    dis[k]=0,dfs(0,k);
    //k表示最远的端点
    top=k;//找直径
    for(int i=top,j=top,l=1,r=0;i;i=fa[i]){
        while(dis[j]-dis[i]>m)j=fa[j];
        //进行尺取,选路径。
        x=max(dis[top]-dis[j],dis[i]);
        //路径两端点到直径端点的最小贡献.
        ans=min(ans,x);
    }
    for(int i=top;i;i=fa[i])mark[i]=1;
    //标记直径,重新计算每个点的贡献。
    for(int i=top;i;i=fa[i]){
        k=i,dis[k]=0;
        dfs(fa[i],i);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,dis[i]);
    //每个点的贡献,仔细想想为什么是对的。
    printf("%d\n",ans);
    return 0;
    //去掉注释其实代码还挺短的(*^▽^*) 复杂度可以过BZOJ的数据
}