RXD, tree and sequence

Posted on | In , ,

题目链接

题意

有一棵树，$n$个结点，有$n$一个排列$p$。
现在要求将$p$分成$k$段，每段求出$lca$后使得每段$lca$深度和最小。

思路

很明显是一道dp。状态也很容易想到用$dp[i][j]$表示前$i$个数字已经划分了$j$段。
要知道一个性质是，每次在一段区间末尾加入一个数字后，值是不增的。

第一种dp

所以我们不妨假设$p[i]$加入$p[j]$时不会产生影响。直接$dp[i][j]=dp[i - 1][j].$
实际上我们知道这是有条件的，也就是要求$p[i]$与$p[i-1]$的$lca$在这段区间里是不起决定性作用的，那我们这样暴力按照相等转移是对的么？
不要着急，其实我们本来不应该直接$dp[i][j] = dp[i - 1][j]$，但是由于这个答案是不增的，所以要么这个式子满足，要么会有更优的答案来代替它。现在我们来看一下其他可能更优秀的转移。
（我个人觉得上面这个比较难理解）
如上所述，第一种情况，$dp[i][j]=dp[i-1][j].$
第二种情况，$p[i]$单独成段，$dp[i][j]=dp[i-1][j-1]+dep(p[i]).$
第三种情况，如果$p[i]$是起决定性作用的点，那么这段区间的$lca$可由它和区间里任意一个点的$lca$得到。
我们不妨就用$p[i-1]$，$dp[i][j]=dp[i-2][j-1]+dep(lca(p[i], p[i-1])).$

上面三种情况去最小就好了。

不知道为什么，用邻接表一直WA，改前向星就过了，我这可怜的一个小时就这样过去了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 3e5 + 5;
struct Edge {
    int v, nxt;
} E[N * 2];
int head[N];
int cnt = 0;
void add(int u, int v) {
    E[cnt].v = v;
    E[cnt].nxt = head[u];
    head[u] = cnt++;
}
int tot, ver[2 * N], deep[2 * N], first[N], lcy[2 * N][30], dir[N];

void dfs(int u, int f, int dep)
{
    first[u] = ++tot;
    ver[tot] = u;
    deep[tot] = dep;
    dir[u] = dep;
    for (int it = head[u]; ~it; it = E[it].nxt)
    {
        int v = E[it].v;
        if (v == f)
            continue;
        dfs(v, u, dep + 1);
        ver[++tot] = u;
        deep[tot] = dep;
    }
}

void ST()
{
    for (int i = 1; i <= tot; i++)
        lcy[i][0] = i;
    for (int j = 1; (1 << j) <= tot; j++)
    {
        for (int i = 1; i + (1 << j) < tot; i++)
        {
            int a = lcy[i][j - 1], b = lcy[i + (1 << (j - 1))][j - 1];
            lcy[i][j] = deep[a] < deep[b]? a : b;
//            dbg(i, j, lcy[i][j]);
        }
    }
}

int RMQ(int l, int r)
{
    int k = 31 - __builtin_clz(r - l + 1);
    int a = lcy[l][k], b = lcy[r - (1 << k) + 1][k];
//    dbg(lcy[l][k], lcy[r - (1 << k) + 1][k]);
    if (deep[a] < deep[b])
        return a;
    else
        return b;
}

int lca(int x, int y)
{
    int a = first[x], b = first[y];
//  dbg(a, b);
    if (a > b)
        swap(a, b);
    return ver[RMQ(a, b)];
}

vector<vector<int> >dp;
int p[N];
int main()
{
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        tot = 0;
        cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &p[i]);
            head[i] = -1;
        }
        for (int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dp.resize(n + 1);
        for (int i = 0; i <= n; i++)
        {
            dp[i].resize(k + 1);
            for (int j = 1; j <= k; j++)
                dp[i][j] = 0x3f3f3f3f;
        }
        dfs(1, 0, 1);
        ST();
//        puts("ove1r");
        dp[0][0] = 0;
//        dbg(lca(4, 6));
//        puts("over2");
//        /*
        for (int j = 1; j <= k; j++)
        {
            for (int i = j; i <= n; i++)
            {
//                dbg(j, i);
                dp[i][j] = dp[i - 1][j];
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + dir[p[i]]);
                if (i - 1 >= j)
                    dp[i][j] = min(dp[i][j], dp[i - 2][j - 1] + dir[lca(p[i], p[i - 1])]);
//                dbg(i, j, dp[i][j], first[p[i]], lca(p[i], p[i - 1]));
            }
        }
        printf("%d\n", dp[n][k]);
//        */
    }
    return 0;
}

第二种 cdq分治

这也是标程的做法，我在赛中也是想过加速$k$层dp的，但是没想出怎么单调来。
这个做法其实也是用了前面的性质，即将一段区间$B$加在区间$A$的后面，$B$的$lca$有可能是具有决定性的，也可能不是。
只有这两种可能，我们在cdq分治的时候可以将$l$到$mid$区间分成两部分，一部分是和$mid+1$到$i$拼接起来后$lca$与后半段无关的。另外一部分是要将两部分取$lca$的。这两种情况的分界点，经过观察具有单调性。于是我们就可以用cdq分治在$O(nklogn)$的时间内解决了。

参考博客

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 3e5 + 5;
struct node
{
	int v, nxt;
}edge[N * 2];
int tot, head[N];

void add_edge(int u, int v)
{
	edge[++tot].v = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

int first[N], dep[2 * N], st[2 * N][30], ord[2 * N];
int cur = 0;
void dfs(int u, int f, int d)
{
	dep[u] = d;
	first[u] = ++cur;
	st[cur][0] = cur;
	ord[cur] = u;
	for (int it = head[u]; ~it; it = edge[it].nxt)
	{
		int v = edge[it].v;
		if (v == f)
			continue;
//		dbg(u, v);
		dfs(v, u, d + 1);
		st[++cur][0] = cur;
		ord[cur] = u;
	}
}

void ST()
{
	for (int j = 1; (1 << j) <= cur; j++)
		for (int i = 1; i + (1 << j) <= cur + 1; i++)
		{
			int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
			st[i][j] = dep[ord[a]] < dep[ord[b]] ? a : b;
//			dbg(i, j, dep[ord[st[i][j]]]);
		}
}

int RMQ(int l, int r)
{
	int k = 31 - __builtin_clz(r - l + 1);
	int a = st[l][k], b = st[r - (1 << k) + 1][k];
	if (dep[ord[a]] < dep[ord[b]])
		return ord[a];
	else
		return ord[b];
}

int lca(int u, int v)
{
	int x = first[u], y = first[v];
	if (x > y)
		swap(x, y);
	return RMQ(x, y);
}

vector<vector<int> > dp;
int p[N];
int a[N], b[N], c[N];

void cdq(int l, int r, int k)
{
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	cdq(l, mid, k);
	a[mid] = p[mid];
	a[mid + 1] = p[mid + 1];
	for (int i = mid - 1; i >= l; i--)
		a[i] = lca(a[i + 1], p[i]);
	for (int i = mid + 2; i <= r; i++)
		a[i] = lca(a[i - 1], p[i]);
	for (int i = mid + 1; i <= r; i++)
		dp[i][k] = min(dp[mid][k - 1] + dep[a[i]], dp[i][k]);
	b[l] = 0x3f3f3f3f;
	for (int i = l + 1; i <= mid; i++)
		b[i] = min(b[i - 1], dp[i - 1][k - 1] + dep[a[i]]);
	c[mid + 1] = 0x3f3f3f3f;
	for (int i = mid; i >= l + 1; i--)
		c[i] = min(c[i + 1], dp[i - 1][k - 1]);
	int tmp = lca(a[mid], a[mid + 1]);
	int pos = mid;
	while (pos > l && dep[a[pos]] > dep[tmp])
		pos--;
	for (int i = mid + 1; i <= r; i++)
	{
		if (dep[a[i]] < dep[tmp])
			tmp = lca(tmp, p[i]);
		while (pos > l && dep[a[pos]] > dep[tmp])
			pos--;
		dp[i][k] = min(dp[i][k], c[pos + 1] + dep[tmp]);
		dp[i][k] = min(dp[i][k], b[pos]);
	}
	cdq(mid + 1, r, k);
}

void init(int n, int k)
{
	for (int i = 1; i <= n; i++)
		head[i] = -1;
	tot = cur = 0;
	dp.resize(n + 1);
	for (int i = 0; i <= n; i++)
		dp[i].resize(k + 1);
}

int main()
{
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &p[i]);
		init(n, k);
		for (int i = 1; i < n; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			add_edge(u, v);
			add_edge(v, u);
		}
		dfs(1, 0, 1);
		ST();
		dp[0][0] = 0;
		for (int i = 0; i <= n; i++)
			for (int j = 1; j <= k; j++)
				dp[i][j] = 0x3f3f3f3f;
		int tmp = p[1];
		for (int i = 1; i <= n; i++)
		{
			tmp = lca(tmp, p[i]);
			dp[i][1] = dep[tmp];
		}
		for (int kk = 2; kk <= k; kk++)
			cdq(1, n, kk);
		printf("%d\n", dp[n][k]);
	}
	return 0;
}

0%