ZOJ 3649 Social Net：最大生成树+树上倍增 DP

This blog post is only available in Simplified Chinse.

Problem

There are $n$ individuals $(2 <= n <= 30000)$ . Everyone has one or more friends. And everyone can contact all people by friend-relation. If two persons aren't friends, they also can contact by their friends. Each pair of friends have a friendship value $a_i$ $(1 <= a_i <= 50000)$ . Firstly, you will relieve some friend-relation. The rest of the friend-relation is the social net. The net is unique in all test cases. In this net, everyone can contact all people by rest friend-relation. The net has a minimum number of friend-relation. And the net has maximum sum of friendship value. We want to get the maximum sum. Secondly, everyone has an angry value $bi$ $(1 <= b_i <= 100000)$ . We have $q$ operations $(1 <= q <= 30000)$ : Person $X$ wants to contact person $Y$ , this operation merely has one sequence which describes the process. The sequence consists of persons' angry value. The persons are on the process. We suppose the sequence is $c_1, c_2, c_3, ... ,c_i$ . Here $c_i$ means the angry value of the $i$ th people in the sequence. We attempt to find the maximum $c_k-c_j$ $(c_k >= c_j, j <= k)$ .

Example: The sequence is 3(X), 4, 5, 6, 7, 5, 9, 4, 11(Y). The maximum $c_k-c_j$ is 11-3=8. The sequence is 3(X), 4, 5, 6, 7, 5, 9, 2, 11(Y). The maximum $c_k-c_j$ is 11-2=9. The sequence is 3(X), 10, 2, 5(Y). The maximum $c_k-c_j$ is 10-3=7.

Input

The input contains multiple test cases. Each test case begins with a line containing a single integer $n$ . The following line contains $n$ integers $b_i$ . The subsequent line describe the number of relations $m$ $(n <= m <= 50000)$ . The next $m$ lines contain the information about relations: $x$ , $y$ , $a_i$ . Their friendship value is $a_i$ . Afterward gives $q$ . The next $q$ lines contain the operations: $x$ , $y$ . person $X$ wants to contact person $Y$ .

Output

For each case, print maximum sum of friendship value of the net on the first line. The next $q$ lines contain the answers of every operations.

Sample Input

6
3 5 1 7 3 5
7
1 2 5
1 3 6
2 4 7
2 5 8
3 6 9
4 5 1
5 6 2
5
6 1
6 2
6 3
6 4
6 5

Sample Output

Translation

题目意思抽象出来是：给你 $n$ 个点的一张图，先求最大生成树，然后在树里给出一大堆询问，对于每对询问给出两个参数 $x_i,y_i$ ，问你树上这两点之间最短路上 $w(j)-w(i)$ 的最大值，其中要保证 $i <= j$ 。

Analysis

第一问求最大生成树果断的 Kruskal，不用讲了……

第二问，如果直接问我们路径上 $w(j)-w(i)$ 的最大值，很显然可以用树上倍增解决，但是麻烦之处就在于这个 $i \le j$ 。这可怎么办呢？

我们可以用一个分治的思想：如果把 $X$ 到 $Y$ 的路径看成一个数列，那么我们可以从中间割开，左右分别处理出答案，然后最终答案就是这个数列里右边的最大值和左边的最小值之差，和左右答案取个 max。

那么我们自然想到了：维护五个树上倍增数组：

$F(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的点；
$max_num(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的距离内 $w(i)$ 的最大值；
$min_num(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的距离内 $w(i)$ 的最小值；
$dif_upd(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的距离内的差值最大值；
$dif_dwn(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的距离内的反向差值最大值；

什么叫“反向差值”呢？根据 $i \le j$ ，“正向差值”是指对于 $i \le j$ 的差值，“反向差值” 则是对于 $j \le i$ 的差值。

其实思路清晰，写起来并不算麻烦。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30005,maxm=60005,maxe=50005;
int n,m,q,w[maxn],fa[maxn],deep[maxn],sum=0;
int tot=0,lnk[maxn],nxt[maxm],son[maxm];
int f[maxn][20],max_num[maxn][20],min_num[maxn][20],dif_upd[maxn][20],dif_dwn[maxn][20];
bool vis[maxn];
struct Edge{
    int x,y,w;
}e[maxe];
inline int max3(int x,int y,int z){
    return z>max(x,y)?z:max(x,y);
}
inline bool Compare(Edge a,Edge b){
    return a.w>b.w;
}
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline int Abs(int x){
    return x<0?-x:x;
}
inline void add(int x,int y){
    tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
    memset(w,0,sizeof(w));
    memset(fa,0,sizeof(fa));
    memset(deep,0,sizeof(deep));
    memset(f,0,sizeof(f));
    memset(max_num,0,sizeof(max_num));
    memset(min_num,0,sizeof(min_num));
    memset(dif_upd,0,sizeof(dif_upd));
    memset(dif_dwn,0,sizeof(dif_dwn));
    tot=0;sum=0;
    memset(lnk,0,sizeof(lnk));
    memset(nxt,0,sizeof(nxt));
    memset(son,0,sizeof(son));
    memset(vis,0,sizeof(vis));
    memset(e,0,sizeof(e));
}
inline int getfa(int x){
    if (fa[x]==x) return x;
    fa[x]=getfa(fa[x]);
    return fa[x];
}
inline void Kruskal(){
    sort(e+1,e+1+m,Compare);
    for (int i=1;i<=n;i++) fa[i]=i;
    int cnt=0;
    for (int i=1;i<=m&&cnt<n-1;i++){
        int fx=getfa(e[i].x),fy=getfa(e[i].y);
        if (fx==fy) continue;
        sum+=e[i].w;
        add(e[i].x,e[i].y);add(e[i].y,e[i].x);
        fa[fx]=fy;cnt++;
    }
    if (cnt!=n-1) printf("ERROR!!!!!\n");
}
inline void BuildTree(int x){
    vis[x]=1;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        fa[son[i]]=x;
        deep[son[i]]=deep[x]+1;
        BuildTree(son[i]);
    }
}
inline void Build(){
    for (int i=1;i<=n;i++){
        f[i][0]=fa[i];
        max_num[i][0]=max(w[i],w[fa[i]]);
        min_num[i][0]=min(w[i],w[fa[i]]);
        dif_upd[i][0]=w[fa[i]]-w[i];dif_dwn[i][0]=w[i]-w[fa[i]];
    }
    for (int j=1;j<20;j++)
        for (int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            max_num[i][j]=max(max_num[i][j-1],max_num[f[i][j-1]][j-1]);
            min_num[i][j]=min(min_num[i][j-1],min_num[f[i][j-1]][j-1]);
            dif_upd[i][j]=max3(dif_upd[i][j-1],dif_upd[f[i][j-1]][j-1],max_num[f[i][j-1]][j-1]-min_num[i][j-1]);
            dif_dwn[i][j]=max3(dif_dwn[i][j-1],dif_dwn[f[i][j-1]][j-1],max_num[i][j-1]-min_num[f[i][j-1]][j-1]);
        }
    // for (int i=1;i<=n;i++){
    //     printf("I=%d -------------\n",i);
    //     for (int j=0;j<19;j++) printf("%d ",f[i][j]);printf("\n");
    //     printf("MAX_NUM: ");for (int j=0;j<19;j++) printf("%d ",max_num[i][j]);printf("\n");
    //     printf("MIN_NUM: ");for (int j=0;j<19;j++) printf("%d ",min_num[i][j]);printf("\n");
    //     printf("DIF_UPD: ");for (int j=0;j<19;j++) printf("%d ",dif_upd[i][j]);printf("\n");
    //     printf("DIF_DWN: ");for (int j=0;j<19;j++) printf("%d ",dif_dwn[i][j]);printf("\n");
    //     printf("\n");
    // }
}
inline int GetAnswer(int x,int y){
    int ret=0;
    int now_min=1e8,now_max=0;
    if (x==y) return 0;
    for (int i=19;i>=0;i--) if (deep[f[x][i]]>=deep[y]){
        ret=max3(ret, max_num[x][i]-now_min, dif_upd[x][i]);
        now_min=min(now_min,min_num[x][i]);
        x=f[x][i];
    }
    for (int i=19;i>=0;i--) if (deep[f[y][i]]>=deep[x]){
        ret=max3(ret, now_max-min_num[y][i], dif_dwn[y][i]);
        now_max=max(now_max,max_num[y][i]);
        y=f[y][i];
    }
    if (x==y) return ret;
    for (int i=19;i>=0;i--) if (f[x][i]!=f[y][i]){
        ret=max3(ret,dif_upd[x][i],dif_dwn[y][i]);
        ret=max3(ret,max_num[x][i]-now_min,now_max-min_num[y][i]);
        now_min=min(now_min,min_num[x][i]);
        now_max=max(now_max,max_num[y][i]);
        x=f[x][i];y=f[y][i];
    }
    ret=max3(ret,dif_upd[x][0],dif_dwn[y][0]);
    ret=max3(ret,max_num[x][0]-now_min,now_max-min_num[y][0]);
    now_min=min(now_min,min_num[x][0]);
    now_max=max(now_max,max_num[y][0]);
    ret=max(ret,now_max-now_min);
    return ret;
}
int main(){
    while (scanf("%d",&n)!=-1){
        Init();
        for (int i=1;i<=n;i++) w[i]=read(),fa[i]=i;
        m=read();
        for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].w=read();
        Kruskal();printf("%d\n",sum);

        memset(fa,0,sizeof(fa));
        deep[1]=1;BuildTree(1);
        //printf("Deep:");for (int i=1;i<=n;i++) printf("%d ",deep[i]);printf("\n");
        //for (int i=1;i<=n;i++) printf("fa[%d]=%d\n",i,fa[i]);printf("\n");

        Build();
        q=read();
        for (int i=1;i<=q;i++){
            int x=read(),y=read();
            printf("%d\n",GetAnswer(x,y));
        }
    }
    return 0;
}

8/3/2018