Highway

原题：Highway

原题大意

n个城市要建造(n-1)条路，求最贵的建造方法。

算法分析

两次dfs求出直径，然后lca更新答案

程序代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=100005;
int fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005];
ll dep[maxn];
struct nod
{
    int to;
    ll cost;
};
int n,m,d1,d2;
vector<nod> g[maxn];
int cnt,sum;
void mkST()
{
    for(int i=1;i<=cnt;i++)st[i][0]=se[i];
    for(int j=1;(1<<j)<=cnt;j++)
        for(int i=1;i<=cnt-(1<<j)+1;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

void DFS(int u,int f,ll di)
{
    dep[u]=di;
    no[++sum]=u;
    int t=sum;
    se[++cnt]=t;
    fir[u]=cnt;
    for(auto p : g[u])
    {
        if(p.to==f)continue;
        DFS(p.to,u,di+p.cost);
        se[++cnt]=t;
    }
}

int find(int p,int q)
{
    if(p>q)swap(p,q);
    int j=lo[q-p+1];
    return min(st[p][j],st[q-(1<<j)+1][j]);
}

ll cal(int x,int y)
{
    int now=no[find(fir[x],fir[y])];
    return dep[x]+dep[y]-2*dep[now];
}
int main()
{
freopen("input.txt", "r", stdin);
    lo[1]=0;
    for(int i=2;i<=200000;i++)lo[i]=lo[i>>1]+1;
    while(scanf("%d", &n) != EOF)
    {
        for(int i=0;i<=n;i++)g[i].clear(),dep[i]=0;
        cnt=sum=0;
        for(int i=1;i<=n-1;i++)
        {
            int x,y;
            ll z;
            scanf("%d%d%lld",&x,&y,&z);
            g[x].pb({y,z});g[y].pb({x,z});
        }
        DFS(1,0,0);mkST();
        vector<int> vex;

        //端点一定只有一边与它相连
        for(int i = 1; i <= n; i++)
            if(g[i].size() == 1)
                vex.pb(i);
        d1 =vex[0];
        ll dis = 0;
        for(int i = 1; i < vex.size(); i++){
            ll len = cal(vex[0], vex[i]);
            if(len > dis){
                d1 = vex[i];
                dis = len;
            }
        }
        dis = 0;
        for(int i = 0; i < vex.size(); i++){
            ll len = cal(d1, vex[i]);
            if(len > dis){
                d2 = vex[i];
                dis = len;
            }
        }
        ll ans = cal(d1, d2);
        for(int i = 1; i <= n; i++){
            if(i == d1 || i == d2) continue;
            ll dis1 = cal(d1,i);
            ll dis2 = cal(d2,i);
            ans+=max(dis1, dis2);
        }
        printf("%lld\n", ans);
    }
    return 0;
}