XTU1267:Highway（LCA+树的直径）

传送门

题意

有n个小镇，Bobo想要建造n-1条边，并且如果在u到v建边，那么花费是u到v的最短路长度（原图），问你最大的花费。

分析

比赛的时候没做出来，QAQ

我们首先要找到树的直径起点和终点，方法是

1.任意选一个点，dfs找到最长路的终点

2.从终点反向dfs，找到起点

然后枚举每个点，用倍增lca求出该点到起点与终点距离，取距离大的，注意直径本身会被访问两次，故一开始ans要减去最长路，时间复杂度O(nlogn)

代码

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int t,n,m;

int fa[100100],depth[100100],up[100100][20],vis[100100];

ll dis[100100],dis2[100100];

struct node

{

    int to;

    ll w;

    node(int tt,ll ww):to(tt),w(ww){}

};

vector<node>edge[100100];

void dfs(int u,int pre,int dep)//第一次dfs，标出每个点的父亲，计算从该点到1的距离dus[i]

{

    depth[u]=dep;//记录深度

    fa[u]=pre;//记录父亲

    int num=edge[u].size();

    R(i,0,num)

    {

        int v=edge[u][i].to;

        if(v!=pre)

        {

            dis[v]=dis[u]+edge[u][i].w;//更新距离

            dfs(v,u,dep+1);

        }

    }

}

void dfs2(int x)//第二次遍历，从第一次dfs的最大距离点遍历

{

    int num=edge[x].size();

    vis[x]=1;//用vis记录该点是否被访问

    R(i,0,num)

    {

        int v=edge[x][i].to;

        if(!vis[v])

        {

            dis2[v]=dis2[x]+edge[x][i].w;//记录距离

            dfs2(v);

        }

    }

}

void create()//构建倍增数组

{

    mem(up,0);

    F(i,1,n) up[i][0]=fa[i];

    for(int j=1;j<20;++j)for(int i=1;i<=n;++i)

        up[i][j]=up[up[i][j-1]][j-1];

}

int lca(int u,int v)//找到u和v的的最近公共祖先

{

    if(depth[u]<depth[v]) swap(u,v);

    int ret=depth[u]-depth[v];

    R(i,0,20)if(ret&(1<<i)) u=up[u][i];//将u调整到与v同深度

    if(u==v) return u;//同一侧，则返回

    for(int i=19;i>=0;--i) if(up[u][i]!=up[v][i])//不同则让u和v向上跳，直到跳不了

    {

        u=up[u][i];

        v=up[v][i];

    }

    return fa[u];

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        int u,v;ll w;

        F(i,0,n) edge[i].clear();

        mem(fa,0);mem(depth,0);

        mem(dis,0);mem(dis2,0);//注意dis和dis2的清空

         for(int i=1;i<n;++i)

        {

            scanf("%d%d%I64d",&u,&v,&w);

            edge[u].push_back(node(v,w));

            edge[v].push_back(node(u,w));

        }

        dfs(1,0,0);

        ll maxx=0;int End,Begin;

        F(i,1,n) if(maxx<dis[i]) { maxx=dis[i];End=i; }//记录从1开始的最长路终点

        create();

        mem(vis,0);

        dfs2(End);

        maxx=0;

        F(i,1,n) if(maxx<dis2[i]) { maxx=dis2[i];Begin=i; }//找到反向dfs最长路的点，那么Begin和End构成树的直径

        ll ans=-maxx;//要遍历树的直径两次，故先减去一次

        F(i,1,n)

        {

            ll ret1,ret2;

            ret1=dis[i]+dis[Begin]-2*dis[lca(i,Begin)];

            ret2=dis[i]+dis[End]-2*dis[lca(i,End)];

            ans+=max(ret1,ret2);//去当前点到直径两端的最短路长度的最大值

        }

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

XTU1267:Highway（LCA+树的直径）

传送门

题意

分析

代码

最新文章

热门文章