XJOI 3629 非严格次小生成树(pqq的礼物)

题目描述：

有一天，pqq准备去给×i×准备礼物，他有一些礼品准备包装一下，他用线将这些礼物连在一起，不同的礼物因为风格不同所以连接它们需要不同价值的线。风格差异越大，价格越大(所以两个礼物之间只有一种连接价格），当然有些礼物实在太不友好，所以有些礼物无法相连。pqq打算把所有礼物打包在一起，他不准备花太多钱，但更不想花最少的钱（免得被拒绝）。所以他想知道第二便宜的包装方案（可重复，pqq会认为这是天命并直接选用最小代价来包装礼物），同时，他还想知道最小的包装代价以向×i×进行炫耀。但是由于pqq不够心灵手巧，所以他准备找你来帮他计算答案。

输入格式：

两个数n，m表示有n个礼物，有m对礼物可以相连1≤n,m≤2∗105

接下来的m行每行三个数a,b,c，表示a礼物和b礼物可以用c的价值相连 , 1≤a,b≤n,1≤c≤106

输出格式：

输出一行，包含两个数，分别是最小代价和次小代价

样例输入：

样例输出：

10 11

瞎扯：我其实很好奇XiX是谁啊┐(´∀｀)┌

题解：其实非严格次小生成树的思路还是很好理解的
首先是什么是非严格次小生成树
就是树边和可以等于和大于最小生成树的另一颗生成树
假设现在要把一条非树边(u,v,c)加入最小生成树，想必要去掉一条原生成树中u->v的边，显然去掉最大边效果是最好的
所以在最小生成树上跑一个倍增DP，d[i][j]表示j的2^i次祖先到j的路径中最大的值
显然可以跟跳lca一样的在logn的跳出u->v路径上的最大值，当然树链剖分也是可以搞这个东西的，但是再写一颗线段树还享受lognlogn的复杂度
emmmm，何必呢……
如果能跳出这个值，我们只要枚举每一条非树边，就可以在nlogn的复杂度里跳出非严格次小生成树，然后就A掉了

代码如下：

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pii pair<int,int>

#define mp make_pair

#define int long long

using namespace std;

int fa[],vis[],deep[],n,m,f[][],d[][],ans1,ans2;

vector<pii> g[];

struct line

{

    int from,to,cost;

}l[];

int cmp(line a,line b)

{

    return a.cost<b.cost;

}

void init()

{

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

    {

        fa[i]=i;

    }

}

int find(int x)

{

    if(fa[x]==x) return x;

    return fa[x]=find(fa[x]);

}

void unity(int t,int x,int y,int c)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy) return ;

    fa[fx]=fy;

    ans1+=c;

    vis[t]=;

    g[x].push_back(mp(y,c));

    g[y].push_back(mp(x,c));

}

void dfs(int now,int ff,int dist,int dep)

{

    d[][now]=dist;

    f[][now]=ff;

    deep[now]=dep;

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

    {

        f[i][now]=f[i-][f[i-][now]];

    }

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

    {

        d[i][now]=max(d[i-][now],d[i-][f[i-][now]]);

    }

    for(int i=;i<g[now].size();i++)

    {

        if(g[now][i].first==ff) continue;

        dfs(g[now][i].first,now,g[now][i].second,dep+);

    }

}

int get(int u,int v)

{

    int x=u,y=v;

    if(deep[x]<deep[y]) swap(x,y);

    int di=;

    for(int i=;i>=;i--)

    {

        if(deep[f[i][x]]>=deep[y])

        {

            di=max(di,d[i][x]);

            x=f[i][x];

        }

    }

    if(x==y) return di;

    for(int i=;i>=;i--)

    {

        if(f[i][x]!=f[i][y])

        {

            di=max(max(d[i][x],d[i][y]),di);

            x=f[i][x];

            y=f[i][y];

        }

    }

    return max(di,max(d[][x],d[][y]));

}

signed main()

{

    scanf("%lld%lld",&n,&m);

    init();

    for(int i=;i<=m;i++)

    {

        scanf("%lld%lld%lld",&l[i].from,&l[i].to,&l[i].cost);

    }

    sort(l+,l+m+,cmp);

    for(int i=;i<=m;i++)

    {

        unity(i,l[i].from,l[i].to,l[i].cost);

    }

    dfs(,,,);

    ans2=1e16;

    for(int i=;i<=m;i++)

    {

        if(!vis[i])

        {

            ans2=min(ans2,ans1+l[i].cost-get(l[i].from,l[i].to));

        }

    }

    printf("%lld %lld\n",ans1,ans2);

}

巴特西