解題區/解題區 - UVa

UVa 13006 - Cake cut

Problem

兩個人均分一個簡單凸多邊形的蛋糕，蛋糕高度為 2。第一個人 $A$ 選擇一個頂點 $u$，第二個人 $B$ 選擇另一個頂點 $v$，兩點連線後，將蛋糕分成兩塊，最大那一塊會被 $A$ 拿走，小的那一塊會被 $B$ 拿走，請問在各自最佳策略下，盡可能拿到最大塊面積的結果為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
5
0  0
3  0
3  1
2  2
0  1
6
0  1
1  0
2  0
3  1
2  2
0  2
4
-100000000  -100000000
100000000  -100000000
100000000  100000000
-100000000  100000000
4
-99999995  -100000000
100000000  -100000000
100000000  99999995
-100000000  100000000

Sample Output

1
2
3
4
7 2
6 3
40000000000000000 40000000000000000
39999999999999975 39999998000000025

Solution

首先，在最佳策略下，當 $u$ 已經固定，接下來選擇頂點 $v$，$B$ 的決定必然要使最小塊最大化，而對於 $A$ 而言，選擇 $B$ 已經使最小塊最大化的所有方法中，使得最大塊最大化。

明顯地兩塊面積近似一半，由於是凸多邊形，可以根據掃描線的方式推動頂點 $v$，使得 $\overline{uv}$ 切分的面積近似一半，對於簡單多邊形面積計算由行列式計算，但行列式計算時的變數呈現環狀，先把首尾變數提出，維護中行列式中間一大段的計算，最後補足首尾變數來計算面積。

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
70
71
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <limits.h>
#include <algorithm>
using namespace std;
struct Pt {
    long long x, y;
    Pt(long long a = 0, long long b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
};
long long cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
long long area2(Pt o, Pt a, Pt b) {
    return llabs(cross(o, a, b));
}
const int MAXN = 262144;
Pt P[MAXN];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld", &P[i].x, &P[i].y);
            P[i+N] = P[i];
        }
        
        long long area = 0;
        for (int i = 2; i < N; i++)
            area += area2(P[0], P[i-1], P[i]);
        
        long long tmp = 0;
        pair<long long, long long> ret(0, 0);
        tmp += P[0].x * P[1].y - P[0].y * P[1].x;
        tmp += P[1].x * P[2].y - P[1].y * P[2].x;
        for (int i = 0, j = 2; i < N; i++) {
            while (1) {
                long long test = tmp + (P[j].x * P[i].y - P[j].y * P[i].x);
                if (llabs(test)*2 >= area)
                    break;
                tmp += P[j].x * P[j+1].y - P[j].y * P[j+1].x;
                j++;
            }
            long long t1, t2, p1, p2;
            t1 = llabs(tmp + (P[j].x * P[i].y - P[j].y * P[i].x));
            t2 = area - t1;
            p1 = llabs(tmp - (P[j-1].x * P[j].y - P[j-1].y * P[j].x)
                           + (P[j-1].x * P[i].y - P[j-1].y * P[i].x));
            p2 = area - p1;
            if (t1 < t2)    swap(t1, t2);
            if (p1 < p2)    swap(p1, p2);
            if (t1 > p1)    t1 = p1, t2 = p2;
            ret = max(ret, make_pair(t1, t2));
            tmp -= P[i].x * P[i+1].y - P[i].y * P[i+1].x;
        }
        printf("%lld %lld\n", ret.first, ret.second);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13010 - Galactic taxes

Problem

ACM 辦公室在銀河的各處，辦公室編號 $1$ 到 $N$，辦公室 $i$ 和辦公室 $j$ 之間的移動費用隨著時間 $t$ 成線性關係，假設移動不消耗時間，請決定移動時間 $t$，從辦公室 $1$ 移動到辦公室 $N$ 請問最少花費為何。

給定時間必須在一天以內完成，意即 $0 \le t \le 24 \times 60$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2  1
1  2  1  0
5  8
1  2  27  610658
2  3  -48  529553
3  4  -6  174696
4  5  47  158238
3  5  84  460166
1  3  -21  74502
2  4  -13  858673
1  5  -90  473410
3  3
1  2  1  0
2  3  1  0
1  3  -1  1440
4  5
1  2  1  0
2  4  2  0
1  4  0  500
1  3  -1  1440
3  4  -2  2880
2  1
1  2  0  0

Sample Output

1
2
3
4
5
1440.00000
419431.27273
960.00000
500.00000
0.00000

Solution

明顯地，每一條邊花費都呈現線性關係，假設一張圖只有一條邊，依序加入新的邊進去，時間 $t$ 對應的路徑花費呈現凹性，因此三分搜尋時間 $t$，做一次 Dijkstra $\mathcal{O}(V \log E)$。由於需要精準度到小數五位，估計要到至少三分 50 次，總時間複雜度 $\mathcal{O}(100 V \log E)$。

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
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXV = 2048;
const int MAXE = 131072;
const long long INF = 1e+60;
struct Edge {
    int to, eid;
    double w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
double dist[MAXV];
void addEdge(int x, int y, double v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, double dist[], int n) {
    typedef pair<double, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int I[MAXE], J[MAXE], A[MAXE], B[MAXE];
double f(int N, int M, double t) {
    e = 0;
    for (int i = 1; i <= N; i++)
        adj[i] = NULL;
    for (int i = 0; i < M; i++) {
        double cost = t * A[i] + B[i];
        addEdge(I[i], J[i], cost);
        addEdge(J[i], I[i], cost);
    }
    
    dijkstra(1, dist, N);
    return dist[N];
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < M; i++)
            scanf("%d %d %d %d", &I[i], &J[i], &A[i], &B[i]);
        double l = 0, r = 24 * 60, mid, midmid, md, mmd;
        double ret = 0;
        for (int it = 0; it < 100; it++) {
            mid = (l+r)/2;
            midmid = (mid+r)/2;
            md = f(N, M, mid);
            mmd = f(N, M, midmid);
            ret = max(ret, md);
            if (fabs(md - mmd) < 1e-6)
                break;
            if (md < mmd)
                l = mid;
            else
                r = midmid;
        }
        printf("%.5lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13014 - Keep it energized

Problem

有 $N$ 道關卡，每一道關卡需要消耗能量 $E_i$ 才能通過，每一個關卡有能量商店，只能進行一次交易，一旦交易成功，不管先前的剩餘能量為何，直接消耗 $C_j$ 元補能量到 $S_j$，請問至少花費多少錢才能闖完所有關卡。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 4
1 2 3 4 5
1 6 5
2 14 10
5 5 4
3 7 5
3 4
14 11 2015
1 14 23
2 11 9
3 1987 1
1 2039 33

Sample Output

1
2
14
-1

Solution

明顯地，維護一個最小堆，每一個元素紀錄 <在哪一關買商店, 累計多少花費, 購買時有多少能量>，隨著掃描線移動，依序出隊那些無法抵達的元素，並且隊首花費就是到這一關的最少花費 $C$，再依序嘗試在新的商店購買能量，累計花費後入隊。

時間複雜度 $\mathcal{O}(N \log M)$

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
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <time.h>
using namespace std;
const int MAXN = 131072;
int E[MAXN];
long long sumE[MAXN];
vector< pair<int, int> > shop[MAXN];
struct ELE {
    long long cost;
    int x, e;
    ELE(long long cost = 0, int x = 0, int e = 0):
    cost(cost), x(x), e(e) {}
    bool operator<(const ELE &v) const {
        if (cost != v.cost)
            return cost < v.cost;
        if (x != v.x)
            return x < v.x;
        return e < v.e;
    }
};
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &E[i]), shop[i].clear();
        for (int i = 0; i < M; i++) {
            int L, S, C;
            scanf("%d %d %d", &L, &S, &C);
            shop[L].push_back(make_pair(S, C));
        }
        
        for (int i = 1; i <= N; i++)
            sumE[i] = sumE[i-1] + E[i];
        
        set<ELE> S;
        for (int i = 1; i <= N; i++) {
            while (!S.empty()) {
                ELE u = *S.begin();
                if (u.e < sumE[i-1] - sumE[u.x-1])
                    S.erase(S.begin());
                else
                    break;
            }
            if (S.empty() && i != 1) {
            } else {
                long long mm = i == 1 ? 0 : S.begin()->cost;
                for (int j = 0; j < shop[i].size(); j++) {
                    pair<int, int> p = shop[i][j];
                    if (p.first >= E[i])
                        S.insert(ELE(mm + p.second, i, p.first));
                }
            }
        }
        while (!S.empty()) {
            ELE u = *S.begin();
            if (u.e < sumE[N] - sumE[u.x-1])
                S.erase(S.begin());
            else
                break;
        }
        if (S.empty())
            puts("-1");
        else
            printf("%lld\n", S.begin()->cost);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13054 - Hippo Circus

Problem

馬戲團河馬過門，單一隻河馬過門需要時間 $T_a$，兩隻河馬疊在一起且滿足總高度小於 $H$，需要花費 $T_b$ 的時間。

不管任何順序過門，請問最少時間為何？

Sample Input

1
2
3
4
5
2
3  5  2  3
3  4  2
3  6  2  3
3  4  2

Sample Output

1
2
Case 1: 6
Case 2: 5

Solution

明顯地，最矮的那隻盡量跟最高的那隻配在一起過門，反之考慮分開過門，看哪一種好就選擇哪一種。

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
#include <bits/stdc++.h>
using namespace std;
int A[131072], used[131072];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, H, Ta, Tb;
        scanf("%d %d %d %d", &N, &H, &Ta, &Tb);
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        sort(A, A+N);
        
        long long ret = 0;
        memset(used, 0, sizeof(used));
        int r = N-1;
        for (int i = 0; i < N; i++) {
            if (used[i] == 1)	continue;
            while (r > i && (A[i] + A[r] >= H || used[r] == 1))
                r--;
            if (r > i && A[i] + A[r] < H && used[r] == 0 && Ta+Ta > Tb) {
                ret += Tb;
                used[r] = used[i] = 1;
            } else {
                ret += Ta;
                used[i] = 1;
            }
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13032 - Marbles in Jars

Problem

有 $N$ 個罐子，其中有一個罐子放置彈珠時，每一個彈珠重量會是其他罐子的 1.1 倍，也就是說其中有一個魔法罐子，在魔法罐子中的彈珠都會特別重。現在限制每一個罐子放置彈珠的數量，請問有多少放置彈珠方案，可以找到魔法罐子。

Sample Input

1
2
3
4
5
6
7
3
3
1 2 3
3
1 2 2
2
2 2

Sample Output

1
2
3
Case 1: 1
Case 2: 0
Case 3: 2

Solution

從題目描述中理解到，要找到魔法罐子最簡單的策略就是每一個罐子都擁有不同數量的彈珠，由於每一個罐子限制彈珠數量不一致，做起來就稍微複雜。

假設先依照可仿製彈珠數量多寡排序，將放置少量的彈珠優先放置在前面，依序討論放入新的罐子又與之前放置不同個數的彈珠的方法數。

定義 dp[i][j] 為前 $i$ 個罐子，其中有一罐放置最多的彈珠 $j$ 個。由於已經由小到大排序好，放入新的罐子，分成兩種情況考慮，其中一種是比 $i$ 個罐子放置更多的彈珠，不然就是放置較少的彈珠數量，數學組合一下即可。時間複雜度 $\mathcal{O}(N M^2)$

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
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M[128];
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &M[i]);
        sort(M+1, M+1+N);
        
        long long dp[128][128] = {};
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M[i]; j++) {
                if (j - (i-1) >= 0) {
                    dp[i][j] = dp[i][j] + dp[i-1][j] * (j - (i-1));
                    dp[i][j] %= MOD;
                }
                for (int k = j+1; k <= M[i]; k++) {
                    dp[i][k] = dp[i][k] + dp[i-1][j];
                    dp[i][k] %= MOD;
                }
            }
        }
        
        long long ret = 0;
        for (int i = 0; i <= M[N]; i++)
            ret = (ret + dp[N][i])%MOD;
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13038 - Directed Forest

Problem

給予一張有向森林圖，要求任兩點若有一條路徑，則兩點不可著相同顏色，請問最少著色數為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3
4  2
1  2
3  4
4  3
1  2
2  3
4  1
7  3
3  6
3  7
1  5

Sample Output

1
2
3
Case 1: 2
Case 2: 4
Case 3: 2

Solution

明顯地，最長路徑長度若為 $L$，至少需要 $L$ 個顏色，因此針對每一個樹根進行最長路徑搜索即可，又由於題目給定森林，把每一個樹根抓出來取最大值即可。複雜度 $\mathcal{O}(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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
vector<int> g[MAXN];
int indeg[MAXN];
int dfs(int u) {
    int ret = 1;
    for (auto &v : g[u])
        ret = max(ret, dfs(v)+1);
    return ret;
}
int solve(int root, int N) {
    return dfs(root);
}
int main() {
    int testcase, cases = 0;
    int N, M, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i <= N; i++)
            g[i].clear(), indeg[i] = 0;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v), indeg[v]++;
        }
        
        int ret = 1;
        for (int i = 1; i <= N; i++) {
            if (indeg[i] == 0)
                ret = max(solve(i, N), ret);
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13005 - Blood groups

Problem

還記得孟德爾遺傳法則嗎？從血型分成 A, B, AB, O 型四種，由三個遺傳因子 A, B, i 兩兩組合而成。而外星人突破孟德爾遺傳法則，由 $N$ 個遺傳因子 (不包含隱性因子 i) 決定表徵，並且一個子代會從 $N$ 個父代分別繼承一個遺傳因子。

現在給予在場 $N$ 個父代分別有哪些遺傳因子 (若沒有告知，則剩餘都是隱性因子 i)，接下來會有 $Q$ 組詢問，問某一個遺傳因子組合是否可以被在場 $N$ 個父代組合而成。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2 1
2 2 1
1 2
0
3 4
1 1
2 2 3
0
1 3
3 2 1 3
2 1 2
2 3 2
4 3
4 2 1 3 4
4 2 1 3 4
1 1
1 2
1 3
2 2 1
0

Sample Output

1
2
3
4
5
6
7
8
N
Y
N
Y
N
Y
Y
N

Solution

每一個父代都提供一個遺傳因子，問最後能不能滿足所有匹配，顯而易見地是一題完美二分匹配。建造 source - 父代 - 遺傳因子 - sink。若某一組詢問需要父代提供遺傳因子 $x$，就去找尋有哪些父代可以提供遺傳因子，並且拉一條邊 父代 - 遺傳因子 x 流量為 1。隱性提供者特別判斷一下即可。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int N, Q, B, x;
    while (scanf("%d %d", &N, &Q) == 2) {
        set< set<int> > S;
        set<int> A[128];
        for (int i = 0; i < N; i++) {
            scanf("%d", &B);
            for (int j = 0; j < B; j++) {
                scanf("%d", &x);
                A[i].insert(x);
            }
            if (B != N)	A[i].insert(0);
        }
        
        for (int i = 0; i < Q; i++) {			
            int source = 2*N+2, sink = 2*N+3;
            g.Init(2*N+5);
            
            int used[128] = {};
            for (int j = 0; j < N; j++)	// parent
                g.Addedge(source, j, 1);
                
            scanf("%d", &B);
            for (int j = 0; j < B; j++) {
                scanf("%d", &x);
                g.Addedge(N+x, sink, 1);
                for (int k = 0; k < N; k++) {
                    if (A[k].count(x)) {
                        g.Addedge(k, N+x, 1);
                        used[k] = 1;
                    }
                }
            }
            
            int allused = 1;
            for (int j = 0; j < N; j++) {
                if (A[j].count(0) && B != N)
                    used[j] = 1;
                allused &= used[j];
            }
            
            if (!allused) {
                puts("N");
                continue;
            }
            
            int flow = g.Maxflow(source, sink);
            puts(flow == B ? "Y" : "N");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12415 - Digit Patterns

Problem

讀入一個 regex，一個主字串 $s$，請問有不同的 $i$ 滿足 $s$ 的子字串 s[j...i] 匹配 regex。

正規表達式長度最多 500，主字串 $s$ 長度最多 $10^7$。

Sample Input

1
2
3
4
6 1(2+3)*4
012345
2 00*(10+100)*
00100

Sample Output

1
2
5
1 2 4 5

Solution

隔了一年才解決它，這一題很明顯地在編譯器的範疇，要將一個 regex 轉換成 NFA 甚至 DFA。一開始設想轉換成 DFA，但長度 500 轉換成 DFA，用狀態壓縮的方式狀態增長非常大，不知道是不是指數成長，上傳就得到 Runtime Error。

將 regex 轉換成 NFA (nondeterministic finite automata) 並不難，但節點會很多且存在很多 $a \overset{\varepsilon}{\rightarrow} b$ 這種類型的邊。在解析 regular expression 時，用線性 $\mathcal{O}(n)$ 或者是 $\mathcal{O}(n^2)$ 都沒關係。因為在計算答案至少 $\mathcal{O}(10^7)$。

得到最原生的 NFA 後，接下來要思考怎麼找到匹配的子字串 $s_{j, i}$，維護可轉移的狀態集合 $S$，若當前 $S$ 中存在 acceptable 狀態，則找到一個 $i$ 解。依序加入字符 $s_i$，維護 $S$ 的做法如下：

  • 將起始狀態丟入 $S$，計算閉包 (closure)，也就是所有 $a \overset{\varepsilon}{\rightarrow} b$ 能連到的狀態都應該被丟入 $S$。
  • 定義下一個狀態集合 $S'$，在 $S$ 中的每一個狀態 $q$，都嘗試藉由 $s_i$ 轉移到 $q'$，將所有 $q'$ 丟入 $S'$ 中。
  • 若 $\text{closure}(S')$ 存在 acceptable 狀態，則 $i$ 是一組解。
  • $S = \text{closure}(S' + \mathit{q}_{start})$。

上面的算法並沒有錯，但原生的 NFA 產生方式在計算閉包時很慢，過多的邊和重複狀態導致。因此需要重建邊，預處理每一個字符轉移，移除所有 $a \overset{\varepsilon}{\rightarrow} b$，這麼一來就能在時限內通過。時間複雜度 $\mathcal{O}(|s| \times (\text{state} + \text{edge}))$

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#include <bits/stdc++.h>
using namespace std;
const int MAXSTATE = 32767;
const int epsilon = 0;
int toIndex(char c) {
    return c - '0' + 1;
}
struct State {
    vector<State*> trans[11];
    int ac, label;
    State() {
        ac = label = 0;
        for (int i = 0; i < 11; i++)
            trans[i].clear();
    }
} _mem[MAXSTATE];
int nodesize = 0;
State *newState() {
    assert(nodesize < MAXSTATE);
    State *p = &_mem[nodesize++];
    *p = State();
    return p;
}
struct NFA {
    State *st, *ac;
    NFA() {
        st = ac = NULL;
    }
    NFA(char c) {
        st = newState(), ac = newState();
        ac->ac = 1;
        st->trans[toIndex(c)].push_back(ac);
    }
    NFA(NFA L, char c) {	// (A)*
        st = ac = NULL;
        if (c != '*')
            return ;
        st = newState(), ac = newState();
        ac->ac = 1;
        st->trans[epsilon].push_back(L.st);
        L.st->trans[epsilon].push_back(L.ac);
        L.ac->trans[epsilon].push_back(L.st);
        L.ac->trans[epsilon].push_back(ac);
        L.ac->ac = 0;
    }
    NFA(NFA L, NFA R, char c) {
        if (R.st == NULL) {
            st = L.st, ac = L.ac;
            return;
        }
        if (c == '|') {
            st = newState(), ac = newState();
            ac->ac = 1;
            st->trans[epsilon].push_back(L.st);
            st->trans[epsilon].push_back(R.st);
            L.ac->trans[epsilon].push_back(ac);
            R.ac->trans[epsilon].push_back(ac);
            L.ac->ac = R.ac->ac = 0;
        } else if (c == '&') {
            st = newState(), ac = newState();
            ac->ac = 1;
            st->trans[epsilon].push_back(L.st);
            L.ac->trans[epsilon].push_back(R.st);
            R.ac->trans[epsilon].push_back(ac);
            L.ac->ac = R.ac->ac = 0;
        }
    }
};
NFA parser(string exp) {
    if (exp.length() == 0)
        return NFA();
    if (exp.length() == 1)
        return NFA(exp[0]);
        
    int l = 0, pos = -1;
    for (int i = 0; i < exp.length(); i++) {
        if (exp[i] == '(') {
            l++;
        } else if (exp[i] == ')') {
            l--;
        } else if (exp[i] == '+') {
            if (l == 0) {
                pos = i;
                break;
            }
        }
    }
    
    if (pos != -1) {
        NFA L = parser(exp.substr(0, pos));
        NFA R = parser(exp.substr(pos+1));
        return NFA(L, R, '|');
    }
    
    int hasStar = 0;
    string ls, rs;
    
    if (exp[0] == '(') {
        for (int i = 0; i < exp.length(); i++) {
            if (exp[i] == '(') {
                l++;
            } else if (exp[i] == ')') {
                l--;
                if (l == 0) {	// (...)...
                    if (i+1 < exp.length() && exp[i+1] == '*') {	// (...)*...
                        hasStar = 1;
                        ls = exp.substr(1, i-1), rs = exp.substr(i+2);
                    } else {	// (...)...
                        ls = exp.substr(1, i-1), rs = exp.substr(i+1);
                    }
                    break;
                }
            }
        }
    } else {	// ...(...) or ...*... or ......
        for (int i = 0; i < exp.length(); i++) {
            if (exp[i] == '(') {
                l++;
            } else if (exp[i] == ')') {
                l--;
            }
            if (l == 0) {
                if (i+1 < exp.length() && exp[i+1] == '*') {
                    hasStar = 1;
                    ls = exp.substr(0, i+1), rs = exp.substr(i+2);
                } else {
                    ls = exp.substr(0, i+1), rs = exp.substr(i+1);
                }
                break;
            }
        }
    }
    for (int i = 0; rs.length() > 0; ) {
        while (i < rs.length() && rs[i] == '*')
            i++;
        rs = rs.substr(i);
        break;
    }
    NFA L = parser(ls);
    NFA R = parser(rs);
    if (hasStar)
        L = NFA(L, '*');
    return NFA(L, R, '&');
}
State *gmap[MAXSTATE];
int relabel(NFA A) {
    int size = 0;
    State *u, *v;
    queue<State*> Q;
    Q.push(A.st), A.st->label = ++size;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        gmap[u->label] = u;
        for (int it = 0; it < 11; it++) {
        	for (int i = 0; i < u->trans[it].size(); i++) {
        		v = u->trans[it][i];
                if (v->label == 0) {
                    v->label = ++size;
                    Q.push(v);
                }
            }
        }
    }
    return size;
}
char s[16777216];
int used[MAXSTATE], ACable[MAXSTATE];
int closure(vector<int> &A, int x, int cases) {
    queue<int> Q;
    State *u;
    int accept = 0;
    if (used[x] != cases)
        A.push_back(x), used[x] = cases;
    Q.push(x);
    while (!Q.empty()) {
        x = Q.front(), Q.pop();
        u = gmap[x];
        accept |= u->ac;
        if (u->trans[epsilon].size() == 0)
            continue;
        for (auto &y : u->trans[epsilon]) {
            if (used[y->label] != cases) {
                Q.push(y->label), used[y->label] = cases;
                A.push_back(y->label);
            }
        }
    }
    return accept;
}
void rebuild(int n, int ctype) {
    memset(ACable, 0, sizeof(ACable));
    memset(used, 0, sizeof(used));
    int cases = 0;
    for (int i = 1; i <= n; i++) {
        cases++;
        vector<int> cc;
        closure(cc, i, cases);
        for (int j = 1; j <= ctype; j++) {
            set<int> S;
            for (int k = 0; k < cc.size(); k++) {
                State *u = gmap[cc[k]];
                for (auto &p : u->trans[j])
                    S.insert(p->label);
                ACable[i] |= u->ac;
            }
            State *u = gmap[i];
            u->trans[j].clear();
            for (auto &x : S)
                u->trans[j].push_back(gmap[x]);
        }
    }
}
int main() {
    int n, m;
    char regex[512];
    while (scanf("%d %s", &n, regex) == 2) {
        nodesize = 0;	// global
        NFA nfa = parser(regex);
        m = relabel(nfa);
        rebuild(m, n);
        scanf("%s", s);
        
        memset(used, 0, sizeof(used));
        int cases = 0, flag = 0;
        
        vector<int> A;
        cases++;
        A.push_back(1);
        for (int i = 0; s[i]; i++) {
            vector<int> next;
            cases++;
            int accept = 0;
            for (int j = 0; j < A.size(); j++) {
                int x = A[j];
                State *u = gmap[x];
                if (u->trans[toIndex(s[i])].size() == 0)
                    continue;
                for (auto &y : u->trans[toIndex(s[i])]) {
                    if (used[y->label] != cases) {
                        used[y->label] = cases, next.push_back(y->label);
                        accept |= ACable[y->label];
                    }
                }
            }
            if (used[1] != cases)
                used[1] = cases, next.push_back(1);
            A = next;
            if (accept) {
                if (flag)	putchar(' ');
                flag = 1;
                printf("%d", i+1);
            }
        }
        puts("");
    }
    return 0;
}
/*
6 1(2+3)*4
012345
2 00*(10+100)*
00100
*/
Read More +
解題區/解題區 - UVa

UVa 11996 - Jewel Magic

Problem

給定一個字串，支持以下四種操作

  • 1 p c 插入一個字符 c 在位置 p
  • 2 p 刪除位置 p 的字符
  • 3 p1 p2 反轉區間 [p1, p2]
  • 4 p1 p2 求出子字串的 LCP 最常共同前綴長。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12 9
000100001100
1 0 1
4 2 6
3 7 10
4 1 7
2 9
4 3 11
4 1 9
4 1 7
4 2 3

Sample Output

1
2
3
4
5
6
3
6
2
0
3
2

Solution

前三項很簡單地可以運用一些 treap 和 splay tree 完成，對於第四項則比較麻煩，只能靠二分長度 + hash 操作來完成。

splay tree 中每一個節點表示一個字符，因此中序走訪就是原本的字串。由於需要反轉操作，需要維護反轉標記，由於要維護 hash 值，需要額外維護一個前綴 hash 值，由於搭配反轉標記，必要時維護後綴 hash 值 (逆序)。

二分 LCP 長度時，就相當於把某個區間從 splay tree 剪下，然後看根的 hash 結果。由於之後還要接回去，實作時利用 splay() 操作，把區間的前一個和後一個節點轉到根和根之下，則區間則會在根的右子樹的左子樹，由於會運用到區間的前一個和後一個，因此維護兩個哨兵字符在字串中 $000001# 方便空節點的判斷。

關於 hash 部分，由於要有點數學合成，不知道一些奇怪的雜湊怎麼用在二元樹長度不固定的接合，可以利用多項式 hash(string) = s0 + s1 x + s2 x^2 + ... 來完成，讓他自動溢位即可，至於 x 的基底就隨便挑吧！

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 400005;
const int SEED = 13;
unsigned long BASE[MAXN];
class SPLAY_TREE { // Splay Tree
public:
    static const int MAXN = 400005;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, size;
        unsigned long h[2];
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = 0, size = 1;
            h[0] = h[1] = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                if (ch[0] != EMPTY)	ch[0]->rev ^= 1;
                if (ch[1] != EMPTY)	ch[1]->rev ^= 1;
                swap(ch[0], ch[1]), swap(h[0], h[1]);
                rev ^= 1;
            }
        }
        void pushup() {
            if (ch[0] != EMPTY)	ch[0]->pushdown();
            if (ch[1] != EMPTY)	ch[1]->pushdown();
            h[0] = ch[0]->h[0] + val*BASE[ch[0]->size] + ch[1]->h[0]*BASE[ch[0]->size+1];
        	h[1] = ch[1]->h[1] + val*BASE[ch[1]->size] + ch[0]->h[1]*BASE[ch[1]->size+1];
            size = 1 + ch[0]->size + ch[1]->size;
        }
    } _mem[MAXN];
    
    int bufIdx;
    SPLAY_TREE::Node *root;
    SPLAY_TREE() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = Node::EMPTY->val = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    Node* find_rt(Node *x) {
        for (; x->fa != Node::EMPTY; x = x->fa);
        return x;
    }
    void splay(Node *x, Node *below) {
        Node *y, *z;
        deal(x);
        while (!x->is_root() && x->fa != below) {
            y = x->fa, z = y->fa;
            if (!y->is_root() && y->fa != below) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
        if (x->fa == Node::EMPTY)	root = x;
    }
    Node* build(int l, int r, Node *p, char s[]) {
        if (l > r)	return Node::EMPTY; 
        int mid = (l + r)/2;
        Node *t = newNode();
        t->val = s[mid], t->fa = p;
        t->ch[0] = build(l, mid-1, t, s);
        t->ch[1] = build(mid+1, r, t, s);
        t->pushup();
        if (p == Node::EMPTY)	root = t;
        return t;
    }
    void debug(Node *u){
        if (u == Node::EMPTY) return;
        u->pushdown();
        debug(u->ch[0]);
        printf("%d", u->val);
        debug(u->ch[1]);
    }
    Node* kthNode(int pos) {
    	Node *u = root;
    	for (int t; u != Node::EMPTY;) {
    		u->pushdown();
    		t = u->ch[0]->size;
    		if (t+1 == pos)	return u;
    		if (t >= pos)
    			u = u->ch[0];
    		else
    			pos -= t+1, u = u->ch[1];
    	}
    	return Node::EMPTY;
    } 
    void insert(int pos, int val) {
    	Node *p, *q, *r;
    	p = kthNode(pos), q = kthNode(pos+1);
    	r = newNode();
    	splay(p, Node::EMPTY);
    	splay(q, root);
    	r->val = val, q->ch[0] = r, r->fa = q;
    	splay(r, Node::EMPTY);
    }
    void erase(int pos) {
    	Node *p, *q;
    	p = kthNode(pos-1), q = kthNode(pos+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	q->ch[0] = Node::EMPTY;
    	splay(q, Node::EMPTY);
    }
    void reverse(int l, int r) {
    	Node *p, *q;
    	p = kthNode(l-1), q = kthNode(r+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	q->ch[0]->rev ^= 1;
    	splay(q->ch[0], Node::EMPTY);
    }
    unsigned long hash(int l, int r) {
    	Node *p, *q;
    	p = kthNode(l-1), q = kthNode(r+1);
    	splay(p, Node::EMPTY), splay(q, root);
    	return q->ch[0]->h[0];
    }
    int lcp(int l, int r) {
    	int ret = 0;
    	int bl = 1, br = root->size - max(l, r), mid;
    	while (bl <= br) {
    		mid = (bl + br)/2;
    		if (hash(l, l+mid-1) == hash(r, r+mid-1))
    			bl = mid+1, ret = mid;
    		else
    			br = mid-1;
    	}
    	return ret;
    }
} tree;
SPLAY_TREE::Node *SPLAY_TREE::Node::EMPTY;
int main() {
    BASE[0] = 1;
    for (int i = 1; i < MAXN; i++)
        BASE[i] = BASE[i-1] * SEED;
    int n, m;
    int cmd, p, c, p1, p2;
    char s[262144];
    while (scanf("%d %d", &n, &m) == 2) {
        scanf("%s", s+1);
        s[0] = 3, s[n+1] = 4;
        for (int i = 1; i <= n; i++)
            s[i] -= '0';
        tree.init();
        tree.build(0, n+1, SPLAY_TREE::Node::EMPTY, s);
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &p, &c);
                tree.insert(p+1, c);
            } else if (cmd == 2) {
                scanf("%d", &p);
                tree.erase(p+1);
            } else if (cmd == 3) {
                scanf("%d %d", &p1, &p2);
                tree.reverse(p1+1, p2+1);
            } else if (cmd == 4) {
                scanf("%d %d", &p1, &p2);
                int t = tree.lcp(p1+1, p2+1);
                printf("%d\n", t);
            } 
//    		tree.debug(tree.root);
//			puts("");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11994 - Happy Painting

Problem

操作有三種

  • 1 x y c 將 x 的父親修改成 y，並且這一條邊的顏色為 c
  • 2 x y c 將 x 到 y 的路徑上的邊都修改成顏色 c
  • 3 x y 回報路徑 x 到 y 上有幾種顏色。

Sample Input

1
2
3
4
5
6
7
8
9
6 6
0 1 1 3 3 0
1 2 1 1 1 1
3 2 3
1 3 2 3
3 2 3
3 5 6
1 6 1 1
3 4 6

Sample Output

1
2
3
4
2 2
1 1
0 0
4 3

Solution

顏色總數不超過 30 種，因此可以使用位元壓縮。這題是之前寫的，所以在找同類的父子關係沒有弄好，可以使用 LCA 去代替那繁複的操作，請參照前幾篇的 Link/Cut Tree 的代碼。

這題很特別的地方在於邊權，由於是有根樹，每個節點的點權可以表示成連接父親的邊權，操作時要特別小心，計算路徑時，不可讓上下父子關係顛倒，否則點權會失效，只有樹根才能使用 mk_root。同樣地，找一條路徑 (x, y) 時，先打通 y 到樹根的路徑，接著把 x 打通到樹根的同時，會到最後一次打通時，會碰到 LCA(x, y)，接著將其路徑上的數值合併。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <bits/stdc++.h> 
using namespace std;
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 131072;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, lazy, sum, size;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = sum = 0, size = 1;
            lazy = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                ch[0]->rev ^= 1, ch[1]->rev ^= 1;
                swap(ch[0], ch[1]);
                rev ^= 1;
            }
            if (lazy != 0) {
                if (ch[0] != EMPTY)	ch[0]->push_add(lazy);
                if (ch[1] != EMPTY)	ch[1]->push_add(lazy);
                lazy = 0;
            }
        }
        void pushup() {
            if (this == EMPTY)	return ;
            sum = val, size = 1;
            if (ch[0] != EMPTY)
                sum |= ch[0]->sum, size += ch[0]->size;
            if (ch[1] != EMPTY)
                sum |= ch[1]->sum, size += ch[1]->size;
        }
        inline void push_deal(int c) {
            if (this == EMPTY)	return ;
            val = c;
        }
        inline void push_add(int c) {
            if (this == EMPTY)	return ;
            val = sum = c;
            lazy = c;
        }
    } _mem[MAXN];
    
    int bufIdx;
    LCT() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
    }
    Node* access(Node *u) {
        Node *v = Node::EMPTY;
        for (; u != Node::EMPTY; u = u->fa) {
            splay(u);
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u)->rev ^= 1, splay(u);
    }
    void cut(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        y->ch[0] = x->fa = Node::EMPTY;
    }
    Node* _cut(Node *rt, Node *x) {
        Node *u, *v;
        mk_root(rt);
        access(x), splay(x);
        for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
        x->ch[0]->fa = x->fa;
        x->fa = x->ch[0] = Node::EMPTY;
        return v;
    }
    void link(Node *x, Node *y) {
        mk_root(x);
        x->fa = y;
    }
    Node* find(Node *x) {
        for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
        return x;
    }
    //
    void alter(Node *x, Node *y, int c) {
        if (x == y)		return ;
        Node *rt = find(x), *fx = Node::EMPTY;
        if (rt != x)
            fx = _cut(rt, x);
        if (x == find(y)) {	// resume
            if (fx != Node::EMPTY)
                link(x, fx);
        } else {
            link(x, y);
            x->push_deal(c);
        }
    }
    void paint(Node *x, Node *y, int c) {
        if (x == y || find(x) != find(y))
            return ;
        Node *u, *v = Node::EMPTY;
        access(y), splay(y);
        for (u = x; u != Node::EMPTY; u = u->fa) {
            splay(u);
            if (u->fa == Node::EMPTY) {
                u->ch[1]->push_add(c), v->push_add(c);
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
    }
    pair<int, int> orPath(Node *x, Node *y) {
        if (x == y || find(x) != find(y))
            return {0, 0};
        pair<int, int> ret;
        Node *u, *v = Node::EMPTY;
        access(y), splay(y);
        for (u = x; u != Node::EMPTY; u = u->fa) {
            splay(u), u->pushdown();
            if (u->fa == Node::EMPTY) {
                ret = {u->ch[1]->size + v->size, u->ch[1]->sum | v->sum};
            }
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return ret;
    }
    void debug(int n) {
        for (int i = 1; i <= n; i++)
            printf("[%2d] l %2d r %2d fa %2d rev %2d, val %d lazy %d, %d\n", i, _mem[i].ch[0] - _mem, 
                                                    _mem[i].ch[1] - _mem,
                                                    _mem[i].fa - _mem, 
                                                    _mem[i].rev,
                                                    __builtin_ffs(_mem[i].val)-1,
                                                    __builtin_ffs(_mem[i].lazy)-1,
                                                    _mem[i].sum);
    }
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[131072], *node_x, *node_y;
int p[131072];
int main() {
    int n, m, x, y, c, u, v, cmd;
    while (scanf("%d %d", &n, &m) == 2) {
        tree.init();
        for (int i = 1; i <= n; i++)
            A[i] = tree.newNode();
        
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            if (p[i])
                A[i]->fa = A[p[i]];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &c);
            if (p[i])
                A[i]->push_deal(1<<c);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d %d", &x, &y, &c);
                tree.alter(A[x], A[y], 1<<c);
            } else if (cmd == 2) {
                scanf("%d %d %d", &x, &y, &c);
                tree.paint(A[x], A[y], 1<<c);
            } else if (cmd == 3) {
                scanf("%d %d", &x, &y);
                pair<int, int> r = tree.orPath(A[x], A[y]);
                printf("%d %d\n", r.first, __builtin_popcount(r.second));
            }
        }
    }
    return 0;
}
Read More +