2015-05-14

SRM 659 Div1 PublicTransitHard

1. Problem
2. Solution

Problem

給一棵樹圖，然後可以放置傳送門與兩地，可以在一地經過傳送門，從另一個地點飛出，請問放置方法有多少種使得最遠兩點移動距離不大於 X。

Solution

看題解作！但我相信仍然是噁心的！

首先需要做樹形 dp 找到最長路徑，保留通過自己子樹最深三條、不通過自己子樹擁有最長路徑。

窮舉所有建設方案 $O(N^2)$，用 $O(log n)$ 時間驗證方案正確性。固定其中一個點 $A$，接著 Dfs 走訪另一點 $B$，$A$ 到 $B$ 之間只會有一條路徑 $A,u_1, u_2, ..., B$，壓縮其中的路徑變成一維，對於中間的每一點找到 hanging value，hanging value 也就是葉子到 u 的最長距離。

假設從 A 到 B 上的點特徵表示成 $(p_0, v_0), (p_1, v_1), (p_2, v_2), ..., (p_n, v_n)$ 其中 $p_i$ 表示從 A 出發的距離，$v_i$ 表示 hanging value。

Example

|        |    |         | ...    |
|        |    |    |    |        |
A(u0) - u1 - u2 - u3 - u4 ... - B(un)
|        |    |    |    |        |
|        |    |    |    |
|        |              Y        
|        X

一個 | 表示子樹的距離 1，從上圖中可以得到 $(p_0, v_0) = (0, 4)$, $(p_1, v_1) = (1, 3)$, $(p_2, v_2) = (2, 2)$, $(p_3, v_3) = (3, 2)$, $(p_4, v_4) = (4, 2)$ …

如果要從 u1 分支 X 抵達 u4 分枝 Y，

經過 u1 - u2 - u3 - u4 的最短距離為 $dist = p_4 - p_1 + v_1 + v_4 = 8$
經過 u1 - A - B - un-1 - ... - u4 的最短距離為 $dist = n - p_4 + p_1 + v_1 + v_4$

特別小心下列情況

| 
|                 |
A(u0) ---------- u1 - u2 - u3 - u4 ... - B(un)
|                /|
|\              / |\      <---- inner longest path > X, Stop Dfs
| \            /    \
|  \          /      \

假設 $X = 5$ 有可能 $v_i \le 5$ 但是內部的最長路徑本身就超過，就要停止 Dfs。

那移動的距離方案為通過、不通過傳送點兩種，任意兩點 p2 > p1，不滿足的方案滿足下列兩等式

$p_2 - p_1 + v_1 + v_2 > X$，轉化變成 $v_1 - p_1 > X - p_2 - v_2$
$LIM = X - (n - p_2 + p_1 + v_1 + v_2) < 0$，為了檢查不滿足，則 LIM 要最小化，則 $v_1 + p_1$ 要最大化。

根據 Dfs 逐漸加點，將問題轉化成 RMQ (對一條不滿足下的情況下，第二條要盡可能滿足，利用最大值找到最慘情況。)。

檢查從新加入的點 u，則查找區間 $[X-p_2-v_2, \infty]$ 的最大值 $v_i+p_i$，帶入得到 $LIM$。若 $LIM \geq 0$，得到建造方案合法。Dfs 傳遞下去時，另一種 $LIM$ (屏除子樹 $v_i$ 的計算會不同) 將會限制最多再往下 $LIM$ 層 ($LIM$ 相當於說距離限制還差多少，當往後搜索時，路徑上的節點計算出的 $LIM$ 會逐漸減少 1，若發上路徑上的所有 $LIM < 0$ 則不合法。)，超過這個限制會造成不經過 u 的兩點最短路徑大於 X。

最後特別小心，如果子樹內的最長路徑大於 X 也要停止走訪！接著就實作持久化線段樹，要完成噁心的樹走訪下，不同狀態的線段樹恢復與傳遞變化。

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
class SegementTree {
public:
    struct Node {
        int l, r, lson, rson;
        int mx;
    } node[1048576];
    int nodesize;
    int init(int l, int r) {
        nodesize = 0;
        int root = build(l, r);
        return root;
    }
    int build(int l, int r) {
        if (l > r)  return 0;
        int k = nodesize++;
        node[k].l = l, node[k].r = r, node[k].mx = -9999;
        node[k].lson = node[k].rson = 0;
        if (l == r) return k;
        int m = (l + r)/2;
        node[k].lson = build(l, m);
        node[k].rson = build(m+1, r);
        return k;
    }
    int change(int p, int x, int val) {
        int k = nodesize++;
        node[k] = node[p];
        node[k].mx = max(node[p].mx, val);
        if (node[k].l == node[k].r) return k;
        int m = (node[k].l + node[k].r)/2;
        if (x <= m)
            node[k].lson = change(node[p].lson, x, val);
        else
            node[k].rson = change(node[p].rson, x, val);
        return k;
    }
    int query(int k, int l, int r) {
        if (l <= node[k].l && node[k].r <= r)
            return node[k].mx;
        int m = (node[k].l + node[k].r)/2;
        if (r <= m)
            return query(node[k].lson, l, r);
        else if (l > m)
            return query(node[k].rson, l, r);
        else
        	return max(query(node[k].lson, l, r), query(node[k].rson, l, r));
    }
} segTree;
const int MAXN = 2048;
const int SHIFT = 4096, MAXR = 8192;	
class PublicTransitHard {
public:
    vector<int> g[MAXN];
    int dp[MAXN][3];
    int dp2[MAXN][2];
    int ret1, ret2, limitX, testA;
    void dfs(int u, int p) {
        dp[u][0] = 0, dp[u][1] = 0, dp[u][2] = 0;
        dp2[u][0] = 0, dp2[u][0] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
            dfs(v, u);
            int d = dp[v][0]+1;
            if (d > dp[u][2])
                dp[u][2] = d;
            if (dp[u][2] > dp[u][1])
                swap(dp[u][2], dp[u][1]);
            if (dp[u][1] > dp[u][0])
                swap(dp[u][1], dp[u][0]);
                
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d > dp2[u][1])
                dp2[u][1] = d;
            if (dp2[u][1] > dp2[u][0])
                swap(dp2[u][0], dp2[u][1]);
        }
    }
    void dfs2(int u, int p, int segId, int depth, int mnLIM) {
        int p2 = depth, v2 = dp[u][0];
        int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
        int LIM = limitX - (depth - p2 + mx + v2);
//		printf("query [%d, oo] = %d\n", limitX - p2 - v2 + 1, mx);
//		printf("testA %d - %d, %d %d, LIM = %d, mx = %d\n", testA, u, p2, v2, LIM, mx);
        if (depth > mnLIM)
            return ;
        if (LIM >= 0 && dp[u][0] + dp[u][1] <= limitX && dp2[u][0] <= limitX) {
//			printf("----- connect %d %d, \n", testA, u);
            if (testA == u)	ret1++;
            else			ret2++;
        }
            
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
                
            int d = dp[v][0]+1;
            if (d != dp[u][0])
                v2 = dp[u][0];
            else
                v2 = dp[u][1];
            
            if (d == dp[u][0]) {
                if (dp[u][1] + dp[u][2] > limitX)
                    continue;
            } else if (d == dp[u][1]) {
                if (dp[u][0] + dp[u][2] > limitX)
                    continue;
            } else {
                if (dp[u][0] + dp[u][1] > limitX)
                    continue;
            }
            
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d == dp2[u][0]) {
                if (dp2[u][1] > limitX)
                    continue;
            } else {
                if (dp2[u][0] > limitX)
                    continue;
            }
            
            
//			printf("dfs %d %d, update [%d] = %d\n", p2, v2, v2 - p2, v2 + p2);
            int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
            int LIM2 = limitX - (depth - p2 + mx + v2);
            int segId3 = segTree.change(segId, v2 - p2 + SHIFT, v2 + p2);
//			printf("dfs %d %d, update [%d] = %d, LIM2 = %d\n", p2, v2, v2 - p2, v2 + p2, LIM2);
            dfs2(v, u, segId3, depth+1, min(mnLIM, depth+LIM2));
        }
    }
    int countValidTeleporters(int N, vector<int> edges, int X) {
        ret1 = ret2 = 0, limitX = X;
        for (int i = 0; i < N; i++)
            g[i].clear();
        
        for (int i = 0; i < edges.size(); i++) {
            int u = i+1, v = edges[i];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        for (int A = 0; A < N; A++) {
            dfs(A, -1);
            int root = segTree.init(0, MAXR);
            testA = A;
//			puts("-----");
            dfs2(A, -1, root, 0, 9999);
        }
        return ret1 + ret2/2;
    }	
};
int main() {
    PublicTransitHard test;
//	int N = 4;
//	int edges[] = {0, 1, 2};
//	int X = 1;
//	int N = 3;
//	int edges[] = {0, 0};
//	int X = 2;
//	int N = 6;
//	int edges[] = {0, 0, 0, 1, 1};
//	int X = 2;
//	int N = 7;
//	int edges[] = {0, 1, 0, 1, 2, 4};
//	int X = 3;
    
//	int N = 16;
//	int edges[] = {0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6};
//	int X = 7;
    
    int N = 56;
    int edges[] = {0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54};
    int X = 12;
    
    int ret = test.countValidTeleporters(N, vector<int>(edges, edges + N - 1), X);
    printf("%d\n", ret);
    return 0;
}

Morris' Blog

SRM 659 Div1 PublicTransitHard

contents

Problem

Solution

Example

More

Code