题目

链接：https://xjoi.net/contest/3536/problem/2

SDOI2009 消防

树网的核线性版本

分析

经典题，有结论：选取的路径一定在直径上。

于是就很好做了，直接dp一下然后再双指针在直径上求一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
inline int inc(int x,int v,int mod){x+=v;return x>=mod?x-mod:x;}
inline int dec(int x,int v,int mod){x-=v;return x<0?x+mod:x;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(int x){if(x==0){putchar(48);return;}int len=0,dg[20];while(x>0){dg[++len]=x%10;x/=10;}for(register int i=len;i>=1;i--)putchar(dg[i]+48);}
const int N=1e6+5,M=2e6+5,MOD=1e9+7;
int n,m,k,maxn,ans=2e9;
int dist[M],f[M],head[M],to[M],val[M],nex[M],idx;
bool vis[M];
void add(int u,int v,int w){
    nex[++idx]=head[u];
    val[idx]=w;
    to[idx]=v;
    head[u]=idx;
    return ;
}
void dfs(int x,int fa){
    f[x]=fa;
    if(dist[x]>dist[k])k=x;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa||vis[y]) continue;
        dist[y]=dist[x]+val[i];
        dfs(y,x);
    }
    return ;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }
    dist[1]=1;
    dfs(1,0);
    dist[k]=0;
    dfs(k,0);
    maxn=k;
    for(int i=maxn,j=maxn;i;i=f[i]){
        while(dist[j]-dist[i]>m) j=f[j];
        ans=min(ans,max(dist[maxn]-dist[j],dist[i]));
    }
    for(int i=maxn;i;i=f[i]) vis[i]=1;
    for(int i=maxn;i;i=f[i]){
        dist[i]=0;
        dfs(i,f[i]);
    }
    for(int i=1;i<=n;i++) ans=max(ans,dist[i]);
    cout<<ans;
    return 0;
}

扩展

其实如果没有路径限制只是一个点的话显然可以dp，同时这样的话还支持带点权和边权。

具体在后面某个t1就是这题。