prow2012-A3-0019

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
这题是改编自{{{http://poj.org/problem?id=3728}}}
题意：给出一棵节点有值的树，给出Q个询问(a,b)，问从a到b的最大盈利
（即：先在最小值买入，再在最大值卖出）

比赛时没发现，现在看懂题意后觉得好眼熟。。。原来在POJ做过类似题，这题只不过多求一个MST。

求好了一棵生成树以后，就是类似一个树形DP的并查集操作（边tarjan求LCA边算答案）

要求出a->b的答案，假设lca(a,b)= fa 
需要得到的是 
a->fa路径上的数值最大值 fmax(a) 
fa->b路径上的数值最小值 fmin(b) 
a->fa路径上的最大盈利(答案) ffrom(a) 
fa->b路径上的最大盈利(答案) fto(b) 
得到这些量后，a->b的答案就等于 max(ffrom(a),fto(b),fmax(a)-fmin(b)) 

如何维护得到这四个量：
{{{
int findroot(int x) {
    if (father[x] == x) return x;
    int fa = father[x];
    father[x] = findroot(father[x]);
    ffrom[x] = max(ffrom[x], ffrom[fa]);
    ffrom[x] = max(ffrom[x], fmax[fa] - fmin[x]);
    fto[x] = max(fto[fa], fto[x]);
    fto[x] = max(fto[x], fmax[x] - fmin[fa]);
    fmax[x] = max(fmax[fa], fmax[x]);
    fmin[x] = min(fmin[fa], fmin[x]);
    return father[x];
}
}}}
在并查集的同时，fa记录下当前的父亲，对fa进行findroot(这样就维护好了fa的正确dp值) 
然后从fa的值DP到当前点x的dp值。维护完毕。


在查询时，需要深刻理解LCA的tarjan思想，而不是会用模板——因为你得知道 
对于a->b的查询，当lca到b时，a的父亲是lca(a,b)，而b的父亲不是！ 

所以对于b->lca(a,b)这一段的dp值，不能通过ffrom[],fto[],fmax,fmin去读取 
而是要一直追溯上去到lca(a,b)为止求得这一段的dp值，无需记录 

}}}

{{{

/* 
 * File:   main.cpp
 * Author: prowindy
 *
 * Created on 2010年11月10日, 下午13:17
 */

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int node[200000], next[200000], edge[100000], tot;
int father[200000], fmax[200000], fmin[200000], Num[200000];
bool lcavis[100000], visit[100000];
int Res[200000];
int ffrom[200000], fto[200000], tfa[200000];
int X[100000],Y[100000],order[100000],cost[100000];
void insert(int a, int b) {
    node[tot] = b, next[tot] = edge[a], edge[a] = tot++;
}
#define PII pair<int,int>
vector<PII> Query[100000];

void initset(int N) {
    for (int i = 0; i <= N; i++) {
        father[i] = i;
        Query[i].clear();
        fmax[i] = fmin[i] = Num[i];
        ffrom[i] = fto[i] = 0;
    }
}

int findroot(int x) {
    if (father[x] == x) return x;
    int fa = father[x];
    father[x] = findroot(father[x]);
    ffrom[x] = max(ffrom[x], ffrom[fa]);
    ffrom[x] = max(ffrom[x], fmax[fa] - fmin[x]);
    fto[x] = max(fto[fa], fto[x]);
    fto[x] = max(fto[x], fmax[x] - fmin[fa]);
    fmax[x] = max(fmax[fa], fmax[x]);
    fmin[x] = min(fmin[fa], fmin[x]);
    return father[x];
}

void Unoin(int a, int b) {
    father[a] = b;
    return;
}
int t, u, i, fa, now, ans, from, to, Max, Min;

void calc(int v) {
    t = Query[v].size();
    for (i = 0; i < t; i++) {
        u = Query[v][i].first;
        if (!visit[u]) continue;
        fa = findroot(u);

        if (Query[v][i].second < 0) {
            now = v;
            to = 0, Max = Num[now];
            while (now != fa&&now!=-1) {
                to = max(to, Max - Num[tfa[now]]);
                Max = max(Max, Num[tfa[now]]);
                now = tfa[now];
            }
            if (now==-1) ans = -1;
            else {
            ans = max(ffrom[u], to);
            ans = max(ans, Max - fmin[u]);
            }
            Res[abs(Query[v][i].second)] = ans;

        } else {
            now = v;
            from = 0, Min = Num[now];
            while (now != fa&&now!=-1) {
                from = max(from, Num[tfa[now]] - Min);
                Min = min(Min, Num[tfa[now]]);
                now = tfa[now];
            }
            if (now==-1) ans = -1;
            else {
            ans = max(fto[u], from);
            ans = max(ans, fmax[u] - Min);
            }
            Res[abs(Query[v][i].second)] = ans;
        }
    }
}

void LCA(int v) {
    lcavis[v] = true;
    for (int i = edge[v]; i != -1; i = next[i])
        if (!lcavis[node[i]]) {
            tfa[node[i]] = v;
            LCA(node[i]);
            Unoin(node[i], v);
        }
    visit[v] = true;
    calc(v);
}

/*
 * 
 */
bool cmp(int i,int j){
    return cost[i]<cost[j];
}
int main(int argc, char** argv) {
    int N, i, a, b, M;
while (scanf("%d", &N) != EOF) {

    memset(edge, -1, sizeof (edge));
    memset(visit, false, sizeof (visit));
    memset(lcavis, false, sizeof (lcavis));
    tot = 0;
    for (i = 1; i <= N; i++)
        scanf("%d", &Num[i]);
    initset(N);
    scanf("%d",&M);
    for (i=0;i<M;i++){
        scanf("%d%d%d",&X[i],&Y[i],&cost[i]);
        cost[i] *=-1;
        order[i] = i;
    }
    sort(order,order+M,cmp);
    int cnt = 0;
    long long ans1 = 0;
    for (i=0;i<M;i++){
        int a = findroot(X[order[i]]),b = findroot(Y[order[i]]);
        if (a!=b){
            father[a] = b;
            cnt++;
            ans1-=cost[order[i]];
            insert(X[order[i]],Y[order[i]]);
            insert(Y[order[i]],X[order[i]]);
            //printf("%d %d\n",X[order[i]],Y[order[i]]);
        }
        if (cnt==N-1) break;
    }
//  if (i==M) while(1);
    initset(N);
    scanf("%d", &M);
    for (i = 1; i <= M; i++) {
        scanf("%d%d", &a, &b);
        Query[a].push_back(make_pair(b, i));
        Query[b].push_back(make_pair(a, -i));
        Res[i] = -1;
    }
    for (i=1;i<=N;i++)
        if (!lcavis[i])
            tfa[i] = -1,LCA(i);
    //printf("%d\n",ans1);
    cout<<ans1<<endl;
    for (i = 1; i <= M; i++)
        printf("%d\n", Res[i]);

    }
    return 0;
}


}}}

这题是改编自{{{http://poj.org/problem?id=3728}}}
题意：给出一棵节点有值的树，给出Q个询问(a,b)，问从a到b的最大盈利
（即：先在最小值买入，再在最大值卖出）
比赛时没发现，现在看懂题意后觉得好眼熟。。。原来在POJ做过类似题，这题只不过多求一个MST。
求好了一棵生成树以后，就是类似一个树形DP的并查集操作（边tarjan求LCA边算答案）
要求出a->b的答案，假设lca(a,b)= fa 
需要得到的是 
a->fa路径上的数值最大值 fmax(a) 
fa->b路径上的数值最小值 fmin(b) 
a->fa路径上的最大盈利(答案) ffrom(a) 
fa->b路径上的最大盈利(答案) fto(b) 
得到这些量后，a->b的答案就等于 max(ffrom(a),fto(b),fmax(a)-fmin(b)) 
如何维护得到这四个量：
{{{
int findroot(int x) {
    if (father[x] == x) return x;
    int fa = father[x];
    father[x] = findroot(father[x]);
    ffrom[x] = max(ffrom[x], ffrom[fa]);
    ffrom[x] = max(ffrom[x], fmax[fa] - fmin[x]);
    fto[x] = max(fto[fa], fto[x]);
    fto[x] = max(fto[x], fmax[x] - fmin[fa]);
    fmax[x] = max(fmax[fa], fmax[x]);
    fmin[x] = min(fmin[fa], fmin[x]);
    return father[x];
}
}}}
在并查集的同时，fa记录下当前的父亲，对fa进行findroot(这样就维护好了fa的正确dp值) 
然后从fa的值DP到当前点x的dp值。维护完毕。
在查询时，需要深刻理解LCA的tarjan思想，而不是会用模板——因为你得知道 
对于a->b的查询，当lca到b时，a的父亲是lca(a,b)，而b的父亲不是！ 
所以对于b->lca(a,b)这一段的dp值，不能通过ffrom[],fto[],fmax,fmin去读取 
而是要一直追溯上去到lca(a,b)为止求得这一段的dp值，无需记录 

/* 
 * File:   main.cpp
 * Author: prowindy
 *
 * Created on 2010年11月10日, 下午13:17
 */
#include <cstdlib>
#include <vector>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int node[200000], next[200000], edge[100000], tot;
int father[200000], fmax[200000], fmin[200000], Num[200000];
bool lcavis[100000], visit[100000];
int Res[200000];
int ffrom[200000], fto[200000], tfa[200000];
int X[100000],Y[100000],order[100000],cost[100000];
void insert(int a, int b) {
    node[tot] = b, next[tot] = edge[a], edge[a] = tot++;
}
#define PII pair<int,int>
vector<PII> Query[100000];
void initset(int N) {
    for (int i = 0; i <= N; i++) {
        father[i] = i;
        Query[i].clear();
        fmax[i] = fmin[i] = Num[i];
        ffrom[i] = fto[i] = 0;
    }
}
int findroot(int x) {
    if (father[x] == x) return x;
    int fa = father[x];
    father[x] = findroot(father[x]);
    ffrom[x] = max(ffrom[x], ffrom[fa]);
    ffrom[x] = max(ffrom[x], fmax[fa] - fmin[x]);
    fto[x] = max(fto[fa], fto[x]);
    fto[x] = max(fto[x], fmax[x] - fmin[fa]);
    fmax[x] = max(fmax[fa], fmax[x]);
    fmin[x] = min(fmin[fa], fmin[x]);
    return father[x];
}
void Unoin(int a, int b) {
    father[a] = b;
    return;
}
int t, u, i, fa, now, ans, from, to, Max, Min;
void calc(int v) {
    t = Query[v].size();
    for (i = 0; i < t; i++) {
        u = Query[v][i].first;
        if (!visit[u]) continue;
        fa = findroot(u);
        if (Query[v][i].second < 0) {
            now = v;
            to = 0, Max = Num[now];
            while (now != fa&&now!=-1) {
                to = max(to, Max - Num[tfa[now]]);
                Max = max(Max, Num[tfa[now]]);
                now = tfa[now];
            }
            if (now==-1) ans = -1;
            else {
            ans = max(ffrom[u], to);
            ans = max(ans, Max - fmin[u]);
            }
            Res[abs(Query[v][i].second)] = ans;
        } else {
            now = v;
            from = 0, Min = Num[now];
            while (now != fa&&now!=-1) {
                from = max(from, Num[tfa[now]] - Min);
                Min = min(Min, Num[tfa[now]]);
                now = tfa[now];
            }
            if (now==-1) ans = -1;
            else {
            ans = max(fto[u], from);
            ans = max(ans, fmax[u] - Min);
            }
            Res[abs(Query[v][i].second)] = ans;
        }
    }
}
void LCA(int v) {
    lcavis[v] = true;
    for (int i = edge[v]; i != -1; i = next[i])
        if (!lcavis[node[i]]) {
            tfa[node[i]] = v;
            LCA(node[i]);
            Unoin(node[i], v);
        }
    visit[v] = true;
    calc(v);
}
/*
 * 
 */
bool cmp(int i,int j){
    return cost[i]<cost[j];
}
int main(int argc, char** argv) {
    int N, i, a, b, M;
while (scanf("%d", &N) != EOF) {
    memset(edge, -1, sizeof (edge));
    memset(visit, false, sizeof (visit));
    memset(lcavis, false, sizeof (lcavis));
    tot = 0;
    for (i = 1; i <= N; i++)
        scanf("%d", &Num[i]);
    initset(N);
    scanf("%d",&M);
    for (i=0;i<M;i++){
        scanf("%d%d%d",&X[i],&Y[i],&cost[i]);
        cost[i] *=-1;
        order[i] = i;
    }
    sort(order,order+M,cmp);
    int cnt = 0;
    long long ans1 = 0;
    for (i=0;i<M;i++){
        int a = findroot(X[order[i]]),b = findroot(Y[order[i]]);
        if (a!=b){
            father[a] = b;
            cnt++;
            ans1-=cost[order[i]];
            insert(X[order[i]],Y[order[i]]);
            insert(Y[order[i]],X[order[i]]);
            //printf("%d %d\n",X[order[i]],Y[order[i]]);
        }
        if (cnt==N-1) break;
    }
//  if (i==M) while(1);
    initset(N);
    scanf("%d", &M);
    for (i = 1; i <= M; i++) {
        scanf("%d%d", &a, &b);
        Query[a].push_back(make_pair(b, i));
        Query[b].push_back(make_pair(a, -i));
        Res[i] = -1;
    }
    for (i=1;i<=N;i++)
        if (!lcavis[i])
            tfa[i] = -1,LCA(i);
    //printf("%d\n",ans1);
    cout<<ans1<<endl;
    for (i = 1; i <= M; i++)
        printf("%d\n", Res[i]);
    }
    return 0;
}