洛谷 P1099 树网的核+P2491 [SDOI2011]消防

写在前面：由于是双倍经验就放一块了，虽然数据范围差的有点大。

题目链接

题意：在树的直径上选择一条长度不超过s的路径使这条路径上的点到树上任意点的最大距离最小。

这题数据好像非常水，我写了上界n^2不考虑多条直径还能过？不知道什么操作。

我就说说我的水法吧。dfs两遍求直径。处理直径上路径到直径两端的距离。然后再处理直径上每个点的最远距离，取min。

正确性显然。

 

#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
inline int read()
{
    register int X=0;register char ch=0;bool flag=0;
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') flag=1;
    for(;isdigit(ch);ch=getchar()) X=(X<<3)+(X<<1)+ch-'0';
    return (flag ? -X : X);
}
inline void write(int x)
{
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
const int N=1e6+5;
vector<pair<int ,int > > e[N];
int dis[N],fa[N],n,m,s,ans=1<<30;
bool vis[N];
void dfs(int u)
{
    int sz=e[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=e[u][i].first;
        if(!vis[v] && fa[u]!=v)
        {
            fa[v]=u;
            dis[v]=dis[u]+e[u][i].second;
            dfs(v);
        }
    }
}
int main()
{
    n=read(),s=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),val=read();
        e[u].push_back(mk(v,val)),e[v].push_back(mk(u,val));
    }
    int l1=1,l2=1;
    dis[l1]=1;
    dfs(l1);
    memset(fa,0,sizeof fa);
    for(int i=1;i<=n;i++) if(dis[i]>dis[l1]) l1=i;
    dis[l1]=0;
    dfs(l1);
    for(int i=1;i<=n;i++) if(dis[i]>dis[l2]) l2=i;
    int j=l2;
    for(int i=l2;i;i=fa[i])
    {
        while(fa[j] && dis[i]-dis[fa[j]]<=s) j=fa[j];
        ans=min(ans,max(dis[j],dis[l2]-dis[i]));
    }
    for(int i=l2;i;i=fa[i]) vis[i]=1;
    for(int i=l2;i;i=fa[i]) dis[i]=0,dfs(i);
    for(int i=1;i<=n;i++) ans=(ans>dis[i] ? ans : dis[i]);
    write(ans);
}