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 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 lines contain the information about relations: , , . Their friendship value is . Afterward gives . The next lines contain the operations: , . person wants to contact person .

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)$ 的最大值，其中要保证。

Analysis

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

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

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

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

$F(i,j)$ 表示从 $i$ 点向上推 $2^j$ 个单位的点；
$max_num(i,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; ch=();
     (ch<||ch>) { (ch==) f=;ch=();}
     (ch>=&&ch<=) ret=ret*+ch-,ch=();
     ret*f;
}
{
     x<?-x:x;
}
{
    tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
{
    (w,,(w));
    (fa,,(fa));
    (deep,,(deep));
    (f,,(f));
    (max_num,,(max_num));
    (min_num,,(min_num));
    (dif_upd,,(dif_upd));
    (dif_dwn,,(dif_dwn));
    tot=;sum=;
    (lnk,,(lnk));
    (nxt,,(nxt));
    (son,,(son));
    (vis,,(vis));
    (e,,(e));
}
{
     (fa[x]==x)  x;
    fa[x]=(fa[x]);
     fa[x];
}
{
    (e,e+m,Compare);
     ( i=;i<=n;i++) fa[i]=i;
     cnt=;
     ( i=;i<=m&&cnt<n;i++){
         fx=(e[i].x),fy=(e[i].y);
         (fx==fy) ;
        sum+=e[i].w;
        (e[i].x,e[i].y);(e[i].y,e[i].x);
        fa[fx]=fy;cnt++;
    }
     (cnt!=n) ();
}
{
    vis[x]=;
     ( i=lnk[x];i;i=nxt[i])  (!vis[son[i]]){
        fa[son[i]]=x;
        deep[son[i]]=deep[x];
        (son[i]);
    }
}
{
     ( i=;i<=n;i++){
        f[i][]=fa[i];
        max_num[i][]=(w[i],w[fa[i]]);
        min_num[i][]=(w[i],w[fa[i]]);
        dif_upd[i][]=w[fa[i]]-w[i];dif_dwn[i][]=w[i]-w[fa[i]];
    }
     ( j=;j<;j++)
         ( i=;i<=n;i++){
            f[i][j]=f[f[i][j]][j];
            max_num[i][j]=(max_num[i][j],max_num[f[i][j]][j]);
            min_num[i][j]=(min_num[i][j],min_num[f[i][j]][j]);
            dif_upd[i][j]=(dif_upd[i][j],dif_upd[f[i][j]][j],max_num[f[i][j]][j]-min_num[i][j]);
            dif_dwn[i][j]=(dif_dwn[i][j],dif_dwn[f[i][j]][j],max_num[i][j]-min_num[f[i][j]][j]);
        }
    
    
    
    
    
    
    
    
    
}
{
     ret=;
     now_min=,now_max=;
     (x==y)  ;
     ( i=;i>=;i--)  (deep[f[x][i]]>=deep[y]){
        ret=(ret, max_num[x][i]-now_min, dif_upd[x][i]);
        now_min=(now_min,min_num[x][i]);
        x=f[x][i];
    }
     ( i=;i>=;i--)  (deep[f[y][i]]>=deep[x]){
        ret=(ret, now_max-min_num[y][i], dif_dwn[y][i]);
        now_max=(now_max,max_num[y][i]);
        y=f[y][i];
    }
     (x==y)  ret;
     ( i=;i>=;i--)  (f[x][i]!=f[y][i]){
        ret=(ret,dif_upd[x][i],dif_dwn[y][i]);
        ret=(ret,max_num[x][i]-now_min,now_max-min_num[y][i]);
        now_min=(now_min,min_num[x][i]);
        now_max=(now_max,max_num[y][i]);
        x=f[x][i];y=f[y][i];
    }
    ret=(ret,dif_upd[x][],dif_dwn[y][]);
    ret=(ret,max_num[x][]-now_min,now_max-min_num[y][]);
    now_min=(now_min,min_num[x][]);
    now_max=(now_max,max_num[y][]);
    ret=(ret,now_max-now_min);
     ret;
}
{
     ((,&n)!=){
        ();
         ( i=;i<=n;i++) w[i]=(),fa[i]=i;
        m=();
         ( i=;i<=m;i++) e[i].x=(),e[i].y=(),e[i].w=();
        ();(,sum);

        (fa,,(fa));
        deep[]=;();
        
        

        ();
        q=();
         ( i=;i<=q;i++){
             x=(),y=();
            (,(x,y));
        }
    }
     ;
}

8/3/2018