COCI 2020/2021 Svjetlo(树形DP)
COCI 2020/2021 Svjetlo
題目大意
求最短的樹上路徑(可以重復經(jīng)過點或邊)長度使得經(jīng)過每個點的次數(shù)滿足給定的奇偶性。樹的大小為
N
N
N。
N
≤
500000
Nle 500000
N≤500000
題解
路徑是可以重復的,簡單的樹形DP可能難以處理,考慮路徑的拼接。設
f
i
,
j
,
k
f_{i,j,k}
fi,j,k?表示第
i
i
i個點的子樹內(nèi)(除了自己)的奇偶性已經(jīng)滿足,且子樹內(nèi)(包括自己)的路徑端點數(shù)有
j
j
j個,第
i
i
i個點的奇偶性為
k
k
k的最短路徑長度,其中
j
∈
{
0
,
1
,
2
}
,
k
∈
{
0
,
1
}
jin{0,1,2},kin{0,1}
j∈{0,1,2},k∈{0,1}。轉(zhuǎn)移的時候有很多種情況,但它們都是類似的,端點個數(shù)(狀態(tài)第二維)的轉(zhuǎn)移有:1、兒子子樹內(nèi)均為
0
0
0個端點 –> 自己子樹
0
0
0個端點2、兒子子樹內(nèi)均為
0
0
0個端點 + 自己作為某一個端點 –> 自己子樹內(nèi)
1
1
1個端點3、兒子子樹內(nèi)均為
0
0
0個端點 + 自己作為兩個端點 –> 自己子樹內(nèi)
2
2
2個端點4、一個兒子子樹內(nèi)
1
1
1個端點 + 其他兒子子樹內(nèi)均為
0
0
0個端點 –> 自己子樹內(nèi)
1
1
1個端點5、一個兒子子樹內(nèi)
1
1
1個端點 + 其他兒子子樹內(nèi)均為
0
0
0個端點 + 自己作為某個端點 –> 自己子樹內(nèi)
2
2
2個端點6、一個兒子子樹內(nèi)
2
2
2個端點 + 其他兒子子樹內(nèi)均為
0
0
0個端點 –> 自己子樹內(nèi)
2
2
2個端點7、兩個兒子子樹內(nèi)各
1
1
1個端點 + 其他兒子子樹內(nèi)均為
0
0
0個端點 –> 自己子樹內(nèi)
2
2
2個端點第二維的
j
j
j可以理解為是伸出了多少個“頭”,然后每個子樹相連拼接上,再用剩下的“頭”繼續(xù)往上轉(zhuǎn)移。
0
0
0和
2
2
2都是兩個“頭”,
1
1
1是一個“頭”。兒子之間合并的時候要注意答案所求的是路徑點的個數(shù),所以不能把每個兒子所有“2”都延長
2
2
2的長度到父親,不然兒子之間相接時會算重,而應該少延長一個”頭“,最后更新答案時再只加多
1
1
1。如何保證兒子子樹內(nèi)的奇偶性都滿足條件?如果從兒子節(jié)點尚不滿足奇偶性的點轉(zhuǎn)移時,需要多加上
2
2
2的長度,表示到了父親再往下到兒子走一個來回。至于第三維是轉(zhuǎn)移到當前節(jié)點的
0
0
0還是
1
1
1,需要看轉(zhuǎn)移上來的偶兒子(指
j
j
j為偶數(shù)的兒子)個數(shù)的奇偶性。還要注意,根節(jié)點剩下的兩個“頭”會相連,不僅答案會減
1
1
1,而且對他而言奇偶性還會再多變一次。這樣就做完了嗎?寫到后面可能會很容易忽略的是,這樣寫會默認每個節(jié)點都至少被經(jīng)過一次,而其實并不然,所以根節(jié)點設為任意一個奇偶性條件為
1
1
1的點,同時在枚舉兒子轉(zhuǎn)移時,若整個子樹都已經(jīng)滿足了就直接跳過。
代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500010
int last[N], nxt[N * 2], to[N * 2], len = 0;
int f[N][3][2], a[N], s[N];
void add(int x, int y) {
to[++len] = y;
nxt[len] = last[x];
last[x] = len;
}
void dfs(int k, int fa) {
int s0 = 0, s1 = 1e9, s2 = 1e9, s3 = 1e9, s4 = 1e9, s5 = 1e9, s6 = 1e9, s7 = 1e9;
int t0, t1;
if(!a[k]) s[k]++;
for(int i = last[k]; i; i = nxt[i]) if(to[i] != fa) {
int x = to[i];
dfs(x, k);
if(!s[to[i]]) continue;
s[k] += s[to[i]];
t0 = min(s7 + f[x][0][1] + 1, s6 + f[x][0][0] + 3), t1 = min(s6 + f[x][0][1] + 1, s7 + f[x][0][0] + 3);
s6 = t0, s7 = t1;
t0 = min(s2 + f[x][1][1], s3 + f[x][1][0] + 2), t1 = min(s3 + f[x][1][1], s2 + f[x][1][0] + 2);
s6 = min(s6, t0), s7 = min(s7, t1);
t0 = min(s5 + f[x][0][1] + 1, s4 + f[x][0][0] + 3), t1 = min(s4 + f[x][0][1] + 1, s5 + f[x][0][0] + 3);
s4 = t0, s5 = t1;
t0 = min(s1 + f[x][2][1] + 1, s0 + f[x][2][0] + 3), t1 = min(s0 + f[x][2][1] + 1, s1 + f[x][2][0] + 3);
s4 = min(s4, t0), s5 = min(s5, t1);
t0 = min(s3 + f[x][0][1] + 1, s2 + f[x][0][0] + 3), t1 = min(s2 + f[x][0][1] + 1, s3 + f[x][0][0] + 3);
s2 = t0, s3 = t1;
t0 = min(s0 + f[x][1][1], s1 + f[x][1][0] + 2), t1 = min(s1 + f[x][1][1], s0 + f[x][1][0] + 2);
s2 = min(s2, t0), s3 = min(s3, t1);
t0 = min(s1 + f[x][0][1] + 1, s0 + f[x][0][0] + 3), t1 = min(s0 + f[x][0][1] + 1, s1 + f[x][0][0] + 3);
s0 = t0, s1 = t1;
}
f[k][0][a[k]] = s1 + 1;
f[k][0][a[k] ^ 1] = s0 + 1;
f[k][1][a[k]] = min(s3, s1) + 1;
f[k][1][a[k] ^ 1] = min(s2, s0) + 1;
f[k][2][a[k]] = min(min(s0 + 2, s5 + 1), min(s6 + 2, s2 + 2));
f[k][2][a[k] ^ 1] = min(min(s1 + 2, s4 + 1), min(s7 + 2, s3 + 2));
}
int main() {
int n, i, x, y;
scanf("%d
", &n);
for(i = 1; i <= n; i++) {
a[i] = getchar() - '0';
}
for(i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
for(i = 1; i <= n; i++) if(!a[i]) break;
dfs(i, 0);
printf("%d
", f[i][2][0] - 1);
fclose(stdin);
fclose(stdout);
return 0;
}
總結(jié)
以上是生活随笔為你收集整理的COCI 2020/2021 Svjetlo(树形DP)的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Docker运行GUI软件的方法
- 下一篇: Locust学习总结分享