BZOJ1063 - [NOI2008]道路设计

2017/02/16

题目

Z国坐落于遥远而又神奇的东方半岛上,在小Z的统治时代公路成为这里主要的交通手段。Z国共有n座城市,一 些城市之间由双向的公路所连接。非常神奇的是Z国的每个城市所处的经度都不相同,并且最多只和一个位于它东 边的城市直接通过公路相连。Z国的首都是Z国政治经济文化旅游的中心,每天都有成千上万的人从Z国的其他城市 涌向首都。为了使Z国的交通更加便利顺畅,小Z决定在Z国的公路系统中确定若干条规划路线,将其中的公路全部 改建为铁路。我们定义每条规划路线为一个长度大于1的城市序列,每个城市在该序列中最多出现一次,序列中相 邻的城市之间由公路直接相连(待改建为铁路)。并且,每个城市最多只能出现在一条规划路线中,也就是说,任意 两条规划路线不能有公共部分。当然在一般情况下是不可能将所有的公路修建为铁路的,因此从有些城市出发去往 首都依然需要通过乘坐长途汽车,而长途汽车只往返于公路连接的相邻的城市之间,因此从某个城市出发可能需要 不断地换乘长途汽车和火车才能到达首都。我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽 车的次数,而Z国的交通系统的“不便利值”为所有城市的不便利值的最大值,很明显首都的“不便利值”为0。小 Z想知道如何确定规划路线修建铁路使得Z国的交通系统的“不便利值”最小,以及有多少种不同的规划路线的选择 方案使得“不便利值”达到最小。当然方案总数可能非常大,小Z只关心这个天文数字modQ后的值。注意:规划路 线1-2-3和规划路线3-2-1是等价的,即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方 案中存在一条规划路线不属于另一个方案。

考虑这样的一个树形 DP: F[i][c][n] 表示做到点 i 时,向子树连 n ([0, 2]) 条边,子树最大链长为 c 的方案数。

可以证明 c 是 log(n) 级的:通过树链剖分构造一个解(该解不一定是最好解,但是提供了一个上界), 那么任意一个点到树根的路径上经过的没建铁路的轻边个数不会超过 log(n) 条。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define out(__u, __it) for(It __it=G[__u];__it;__it=__it->n)
#ifdef LCYTEST
#    define test(_x) { _x }
#else
#    define test(_x) {  ; }
#endif
using namespace std;
typedef unsigned long long ULL;
const int PSIZ = int(2E5 + 1E3);
const int LOG_PSIZ = 21; // log_2(2E6 + 1E3) = 20.93
int N, M; ULL Q;

struct tgno {
    int v;
    tgno* n;
} POOL[PSIZ]; int ppos = 0;
tgno* G[PSIZ];
typedef tgno* It;

void _add(int u, int v) {
    POOL[ppos].v = v; POOL[ppos].n = G[u];
    G[u] = &POOL[ppos++];
}

void addEdge(int u, int v) {
    _add(u, v); _add(v, u);
}

int c = 0;
int F[PSIZ][LOG_PSIZ][3];
ULL TDP(int cur, int pre) {
    F[cur][c][0] = 1;
    out(cur, i) {
        if(i->v == pre) continue;
        TDP(i->v, cur);
        ULL Ta = (F[i->v][c-1][0] + F[i->v][c-1][1] + F[i->v][c-1][2]) % Q;
        ULL Tb = (F[i->v][c][0] + F[i->v][c][1]) % Q;
        
        F[cur][c][2] = (F[cur][c][2] * Ta + F[cur][c][1] * Tb) % Q;
        F[cur][c][1] = (F[cur][c][1] * Ta + F[cur][c][0] * Tb) % Q;
        F[cur][c][0] = (F[cur][c][0] * Ta) % Q;
    }
    return (F[cur][c][2] + F[cur][c][1] + F[cur][c][0]) % Q;
}

int main() {
    int p;
    scanf("%d %d %d", &N, &M, &p);
    Q = p;
    bool flag = 0;
    
    if(M < N-1) { printf("-1\n-1\n"); return 0; }
    if(Q < 10000) { Q *= 1973; flag = 1; }
    
    int u, v;
    for(int i=0;i<M;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    
    ULL ans = 0;
    while(!(ans = TDP(1, 0))) c++;
    if(flag) Q /= 1973;
    printf("%d\n%d\n", c, int(ans % Q));
    test({ getchar(); getchar(); getchar(); });
}