学步园

题意：给定一个n（2<=n<=30000）个点m（n<=m<=50000）条边的无向图，选出权值和最大的生成树，给q（1<=q<=30000）个询问u->v路径上顺序

         得到的ci cj（i <= j）的cj - ci最大值是多少。

题解：kruskal搞掉最大生成树，并查集维护up[] dw[] ma[] mi[] 分别表示从当前点走到lca的最优值，从lca走到当前点的最优值，从当点走到lca的最大值，

         从lca走到当前点的最小值即可。 

         PS：比赛的时候把并查集搞错了唉，但是还是搞到了这个fb。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
#define MIN(a , b) ((a) < (b) ? (a) : (b))
using namespace std;
const int maxm = 50002;
const int maxn = 30002;
struct record
{
    int u,v,w;
    bool operator < (const record &other) const
    {
        return w > other.w;
    }
}EE[maxm];
struct node
{
    int v;
    int next;
}edge[maxn << 1];
struct QQ
{
    int u,v,id;
    int next;
}query[maxn << 1];
struct LL
{
    int have,next;
}lca[maxn];
int head[maxn],qhead[maxn],lcahead[maxn];
int angry[maxn],father[maxn],ans[maxn];
int ma[maxn],mi[maxn],up[maxn],dw[maxn];
bool vis[maxn];
int m,n,idx,tot,top,sum;

void swap(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
    return;
}

void init()
{
    memset(head,-1,sizeof(head));
    memset(qhead,-1,sizeof(qhead));
    memset(lcahead,-1,sizeof(lcahead));
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    idx = tot = top = sum = 0;
    return;
}

int gg(int u)
{
    return (u == father[u]) ? father[u] : (father[u] = gg(father[u]));
}

void read()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&angry[i]);
        ma[i] = mi[i] = angry[i];
        up[i] = dw[i] = 0;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&EE[i].u,&EE[i].v,&EE[i].w);
    }
    sort(EE , EE + m);
    return;
}

void addedge(int u,int v)
{
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx++;

    edge[idx].v = u;
    edge[idx].next = head[v];
    head[v] = idx++;
    return;
}

void addquery(int u,int v,int num)
{
    query[tot].u = u;
    query[tot].v = v;
    query[tot].id = num;
    query[tot].next = qhead[u];
    qhead[u] = tot++;

    query[tot].u = v;
    query[tot].v = u;
    query[tot].id = num;
    query[tot].next = qhead[v];
    qhead[v] = tot++;
    return;
}

void kruskal()
{
    for(int i=0;i<m;i++)
    {
        int x = gg(EE[i].u);
        int y = gg(EE[i].v);
        if(x != y)
        {
            sum += EE[i].w;
            father[y] = x;
            addedge(EE[i].u , EE[i].v);
        }
    }
    printf("%d\n",sum);
    return;
}

int find(int u)
{
    if(u == father[u]) return father[u];
    int tmp = father[u];
    father[u] = find(father[u]);
    up[u] = MAX(ma[tmp] - mi[u] , MAX(up[u] , up[tmp]));
    dw[u] = MAX(ma[u] - mi[tmp] , MAX(dw[u] , dw[tmp]));
    ma[u] = MAX(ma[u] , ma[tmp]);
    mi[u] = MIN(mi[u] , mi[tmp]);
    return father[u];
}

void dfs(int st)
{
    vis[st] = true;
    for(int i=qhead[st];i != -1;i=query[i].next)
    {
        if(vis[query[i].v])
        {
            int x = find(query[i].v);
            lca[top].have = i;
            lca[top].next = lcahead[x];
            lcahead[x] = top++;
        }
    }
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        if(vis[edge[i].v] == false)
        {
            dfs(edge[i].v);
            father[edge[i].v] = st;
        }
    }
    for(int i=lcahead[st];i != -1;i=lca[i].next)
    {
        int id = lca[i].have;
        int u = query[id].u;
        int v = query[id].v;
        find(u);
        if(id & 1) swap(u , v);
        ans[query[id].id] = MAX(ma[v] - mi[u] , MAX(up[u] , dw[v]));
    }
    return;
}

void solve()
{
    scanf("%d",&m);
    int u,v;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&u,&v);
        addquery(u,v,i);
    }
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    dfs(1);
    for(int i=0;i<m;i++)
    {
        printf("%d\n",ans[i]);
    }
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        read();
        kruskal();
        solve();
    }
    return 0;
}