Gym - 101473J

题目链接：

http://codeforces.com/gym/101473/attachments

题解：

最大生成树＋树链剖分＋线段树维护最小值

代码：

#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define met(a,b) memset(a,b,sizeof(a))
#define inf 0x7fffffff
const int maxn = 2e5+10;
struct node
{
    int x,y;
    int w;
}num[maxn];
struct node1
{
    int x,y,w;
};
int pre[maxn];
int cntt;
int ans;
vector<node1>len;

int cmp(node a,node b)
{
    return a.w>b.w;
}

int Find(int x)
{
    while(pre[x]!=x)
        return pre[x]=Find(pre[x]);
    return pre[x];
}

void join(int x,int y,int w)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
    {
        node1 now;
        now.x=x;
        now.y=y;
        now.w=w;
        len.push_back(now);
        pre[fx]=fy;
        ans+=w;
        cntt++;
    }
}

// 最大生成树

struct EDGE
{
    int to,next;
}Edge[maxn*2];

struct Tree
{
    int left,right;
    int MIN;
}tree[maxn<<2];
int head[maxn];
int cnt;
void init1()
{
    cnt=0;
    met(head,-1);
}

void Add_edge(int u,int v)
{
    Edge[++cnt].to=v,Edge[cnt].next=head[u],head[u]=cnt;
    Edge[++cnt].to=u,Edge[cnt].next=head[v],head[v]=cnt;
}

int size[maxn],fa[maxn],deep[maxn];
void init2()
{
    met(size,0),met(fa,0),met(deep,0);
}

//size[i]:表示i这个节点下面的字节点的个数

void Dfs1(int x)
{
    size[x]=1;
    for(int i=head[x];i!=-1;i=Edge[i].next)
    {
        if(Edge[i].to==fa[x])
            continue;
        deep[Edge[i].to]=deep[x]+1;
        fa[Edge[i].to]=x;
        Dfs1(Edge[i].to);
        size[x]+=size[Edge[i].to];
    }
}

int bl[maxn],pos[maxn];
int sz;
void init3()
{
    sz=0;
    met(bl,0),met(pos,0);
}

//pos[i]:表示i这个节点在线段树的位置
void Dfs2(int x,int chain)
{
    int k=0;
    sz++;
    pos[x]=sz;//分配在线段树里的位置
    bl[x]=chain;
    for(int i=head[x];i!=-1;i=Edge[i].next)
    {
        if(deep[Edge[i].to]>deep[x]&&size[Edge[i].to]>size[k])
            k=Edge[i].to;//选择子树中的最大的儿子来继承重链
    }
    if(k==0)
        return;
    Dfs2(k,chain);
    for(int i=head[x];i!=-1;i=Edge[i].next)
    {
        if(deep[Edge[i].to]>deep[x]&&k!=Edge[i].to)
            Dfs2(Edge[i].to,Edge[i].to);
    }
}

//－－－－－－－线段树
int room[maxn];
void build(int rt,int l,int r)
{
    tree[rt].left=l;
    tree[rt].right=r;
    if(l==r)
    {
        tree[rt].MIN=room[l];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tree[rt].MIN=min(tree[rt<<1].MIN,tree[rt<<1|1].MIN);
}


int querymin(int x,int y,int rt)
{
    int left=tree[rt].left,right=tree[rt].right,mid=(left+right)>>1;
    if(left==x&&right==y)
        return tree[rt].MIN;
    if(y<=mid)
        return querymin(x,y,rt<<1);
    else if(x>mid)
        return querymin(x,y,rt<<1|1);
    else
        return min(querymin(x,mid,rt<<1),querymin(mid+1,y,rt<<1|1));
}

int slovemin(int x,int y)
{
    int MIN=2e9;
    while(bl[x]!=bl[y])
    {
        if(deep[bl[x]]<deep[bl[y]])
            swap(x,y);
        MIN=min(MIN,querymin(pos[bl[x]],pos[x],1));
        x=fa[bl[x]];
    }
    if(deep[x]>deep[y])
        swap(x,y);
    if(x!=y)
        MIN=min(MIN,querymin(pos[x]+1,pos[y],1));
    return MIN;
}

int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
        pre[i]=i;
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&num[i].x,&num[i].y,&num[i].w);
    sort(num,num+m,cmp);
    cntt=0,ans=0;
    len.clear();
    for(int i=0;i<m;i++)
    {
        join(num[i].x,num[i].y,num[i].w);
        if(cntt==n-1)
            break;
    }
    met(room,0);
    init1(),init2(),init3();
    for(int i=0;i<len.size();i++)
    {
        Add_edge(len[i].x,len[i].y);
    }
    int lenx=(int)len.size();
    Dfs1(1);
    Dfs2(1,1);
    for(int i=0;i<lenx;i++)
    {
        if(deep[len[i].x]>deep[len[i].y])
            room[pos[len[i].x]]=len[i].w;
        else
            room[pos[len[i].y]]=len[i].w;
    }
    room[1]=2e9;
    build(1,1,n);
    while(s--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",slovemin(x,y));
    }

}