Luogu 3647 [APIO 2014] 連珠線

- - - - 傳送門
      - 思路
      - 參考代碼

傳送門

思路

唉，我太弱了，又看錯題了。題目中說一個新的珠子和一個已經添加的珠子連接配接起來，我沒有看到，然後就涼了……

立個 flag：已經連續看錯五題了，後面的題一定要認真看，逐字逐句翻譯讀題。

手玩一下，發現以上重要題意相當于是告訴了我們需要枚舉一個根。發現，如果這是一棵有根樹，那麼藍線的結構就一定不可能是兒子-父親-兒子。因為這種結構的構造方法是先連接配接兒子，再插入父親，但是父親一定要比兒子先加入才行。

是以藍線的結構一定是父親-兒子-孫子。我們可以考慮樹形 DP。我們将結點分成兩類：自由的和被插入的。自由的指這個結點在藍線的兩端，被插入的指這個結點在藍線的中間。

考慮轉移。對于自由的結點，如果它的兒子也是自由的，那麼隻能連紅線；如果它的兒子不是自由的，那麼隻能連藍線。對于被插入的結點，首先要找一個自由的結點連一條藍線，再考慮剩餘結點。若剩餘結點是自由的，那麼隻能連紅線；若剩餘結點是被插入的，也隻能連藍線。

這樣我們就得到了一個 O(n2) O ( n 2 ) 的做法。考慮換根 DP。在我睡了一覺後一次寫過了，是以我就直接講做法了：

設 fi,0/1 f i , 0 / 1 表示以 1 1 為根時 ii 對應的子樹的根結點是自由的/被插入的時的最大答案，這個就是暴力做法用的狀态，狀态轉移方程為：

fi,0=∑max(fto,0,fto,1+cost) f i , 0 = ∑ max ( f t o , 0 , f t o , 1 + c o s t )

fi,1=fi,0+max{fto,0+cost−max(fto,0,fto,1+cost)} f i , 1 = f i , 0 + max { f t o , 0 + c o s t − max ( f t o , 0 , f t o , 1 + c o s t ) }

第二個方程的意思就是選擇一個兒子在自己是自由的情況下仍然加上一條藍邊，使得目前結點為被插入的。顯然最後 1 1 結點對應的答案為 f1,0f1,0。另外，邊界條件為：

fi,0=0 f i , 0 = 0

fi,1=−∞ f i , 1 = − ∞

即：若一個結點是葉結點，那它隻能是自由的，不能使被插入的。

我們設換根 DP 的套路狀态。設 gi,0/1 g i , 0 / 1 表示以 i i 為根，ii 是自由的/被插入的時 i i 的答案。顯然我們最後要求的就是 max{gi,0}max{gi,0}。

這裡我的總結是：顯然隻有 f f 和 gg 是換根 DP 的關鍵資料，但同時換根 DP 往往需要别的資料。這時先不要去考慮要使用什麼别的資料，而是先把 g g 的轉移方程寫出來看看需要什麼（ff 往往不需要别的資料），再來求哪些需要的資料。否則很有可能寫完後才發現之前求的東西根本不需要，甚至會造成混亂。

我們來試着寫一下 g g 的狀态轉移方程：

gi,0=fi,0+???gi,0=fi,0+???

gi,1=max(fi,1+???,fi,0+???) g i , 1 = max ( f i , 1 + ? ? ? , f i , 0 + ? ? ? )

感覺還是挺模糊的，寫不出來，我們試着看看我們究竟要求什麼。

第一個問号求的是 i i 的父結點在不考慮 ii 時的最大答案。我們試着将其設為 Fp,0/1 F p , 0 / 1 ，則得狀态轉移方程：

gi,0=fi,0+max(Fp,0,Fp,1+cost) g i , 0 = f i , 0 + max ( F p , 0 , F p , 1 + c o s t )

其中 cost c o s t 表示父親 p p 到 ii 的邊權。

第二個問号顯然就應該是 max(Fp,0,Fp,1+cost) max ( F p , 0 , F p , 1 + c o s t ) 了，第三個問号顯然就應該是 Fp,0+cost F p , 0 + c o s t 。如果看不懂或者想不到，你可以這樣了解：設 Fp F p 就是把父結點看作一棵自己的子樹時的答案。

是以我們的任務變成了求 F F 。對于 Fi,0Fi,0，我們相當于是排除一棵子樹：

Fi,0=gp,0−max(fi,0,fi,1+cost) F i , 0 = g p , 0 − max ( f i , 0 , f i , 1 + c o s t )

對于 Fi,1 F i , 1 ，我們相當于是要選擇一個兒子強制讓它變成 f0,to+cost f 0 , t o + c o s t ，注意這裡的 to t o 可以是自己的父親。這個強制的變化相當于是在 Fi,0 F i , 0 減去了一個 max(fi,0,fi,1+cost) max ( f i , 0 , f i , 1 + c o s t ) 再加上一個 f0,to+cost f 0 , t o + c o s t ，這會給 Fi,0 F i , 0 帶來一個固定的內插補點。我們找到內插補點的最大值和次大值，則 Fi,1=Fp,0+max{Δ} F i , 1 = F p , 0 + max { Δ } ，特别地，如果最大內插補點來自當且結點，我們就選擇次大內插補點。

看不懂？自己想就好啦！反正我太弱了，代碼太醜了。

參考代碼

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = ; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a *  - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[]; int length = ;
    if (x < ) putchar('-'); else x = -x;
    do buffer[length++] = -(x % ) + '0'; while (x /= );
    do putchar(buffer[--length]); while (length);
}

const LL INF = (~(int() << (sizeof(int) *  - )));
const int maxn = int() + ;
struct Graph
{
    struct Edge
    {
        int to;
        int cost;
        int next;
    } edges[maxn * ];
    int i;
    int head[maxn];
    Graph() : i() { memset(head, -, sizeof(head)); }
    void addEdge(int from, int to, int cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; int cost = e.cost
} G;
int n;

#define RunInstance(x) delete new x
struct brute
{
    LL f[][maxn];
    void DFS(int node, int parent)
    {
        f[][node] = ;
        f[][node] = -INF;
        bool bOk = false;
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;
            DFS(to, node);
            f[][node] += std::max(f[][to], f[][to] + cost);
            bOk = true;
        }
        if (bOk)
        {
            wander(G, node)
            {
                DEF(G);
                if (to == parent) continue;
                f[][node] = std::max(f[][node],
                    f[][node] - std::max(f[][to], f[][to] + cost) +
                    f[][to] + cost);
            }
        }
    }

    brute()
    {
        LL ans = ;
        for (int i = ; i <= n; i++)
        {
            DFS(i, );
            ans = std::max(ans, f[][i]);
        }
        printOut(ans);
    }
};
struct work
{
    LL f[][maxn];
    LL g[][maxn];
    void DFS1(int node, int parent)
    {
        f[][node] = ;
        f[][node] = -INF;
        bool bOk = false;
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;
            DFS1(to, node);
            f[][node] += std::max(f[][to], f[][to] + cost);
            bOk = true;
        }
        if (bOk)
        {
            wander(G, node)
            {
                DEF(G);
                if (to == parent) continue;
                f[][node] = std::max(f[][node],
                    f[][node] - std::max(f[][to], f[][to] + cost) +
                    f[][to] + cost);
            }
        }
    }
    LL F[][maxn];
    void DFS2(int node, int parent, int pc)
    {
        LL major = -INF, minor = -INF;
        int majorIdx = , minorIdx = ;
        if (parent)
        {
            g[][node] = f[][node] + std::max(F[][node], F[][node] + pc);
            g[][node] = std::max(
                f[][node] + std::max(F[][node], F[][node] + pc),
                f[][node] + F[][node] + pc);
            majorIdx = parent;
            major = F[][node] + pc - std::max(F[][node], F[][node] + pc);
        }
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;

            F[][to] = g[][node] - std::max(f[][to], f[][to] + cost);
            LL t = f[][to] + cost - std::max(f[][to], f[][to] + cost);
            if (t > minor)
            {
                if (t > major)
                {
                    minor = major;
                    minorIdx = majorIdx;
                    major = t;
                    majorIdx = to;
                }
                else
                {
                    minor = t;
                    minorIdx = to;
                }
            }
        }
        wander(G, node)
        {
            DEF(G);
            if (to == parent) continue;

            F[][to] = majorIdx == to ? F[][to] + minor : F[][to] + major;
            DFS2(to, node, cost);
        }
    }

    work()
    {
        DFS1(, );
        g[][] = f[][];
        g[][] = f[][];
        DFS2(, , );
        LL ans = ;
        for (int i = ; i <= n; i++)
            ans = std::max(ans, g[][i]);
        printOut(ans);
    }
};

void run()
{
    n = readIn();
    for (int i = ; i < n; i++)
    {
        int from = readIn();
        int to = readIn();
        int cost = readIn();
        G.addEdge(from, to, cost);
        G.addEdge(to, from, cost);
    }

    RunInstance(work);
}

int main()
{
    run();
    return ;
}

Luogu 3647 [APIO 2014] 連珠線

傳送門

思路

參考代碼

繼續閱讀

Luogu 3778 [APIO 2017] 商旅

【BZOJ1179】【APIO2009】Atm（tarjan+spfa）

Luogu 3649 [APIO 2014] 回文串

Luogu 3648 [APIO 2014] 序列分割

【BZOJ5367】【LOJ2308】【APIO2017】商旅（SPFA判負環，01分數規劃，Floyd）

【APIO2010】【樹的直徑】巡邏

【APIO】風鈴(mobiles)

【BZOJ1149】【APIO2007】風鈴（完全二叉樹+dp）

[APIO2010]特别行動隊（斜率優化dp）

BZOJ 2809: [Apio2012]dispatching

Luogu P3622 [APIO2007]動物園

不足萬元的城市小機靈鬼，騎上春風ST PAPIO狒狒你也是“賽車手”

【題解】bzoj1912（同洛谷P3629）[APIO2010]巡邏樹的直徑

[APIO2010]巡邏題解

APIO2010 巡邏樹形DP