[bzoj] 3257: 树的难题

发表于   |   分类于   |  

明明想到了正解然后写跪一分没有 T_T
惨痛教训啊

题意

给出一个无根树,树有N个点,边有权值,每个点都有颜色,是黑色,白色,
灰色这三种颜色之一.
删去若干条边使得树中不含有黑色结点或者含有至多一个白色节点.
计算最小删去边的边权和.

传送门

分析

作为一棵树就要有被树形dp的觉悟 = =
我们设置状态f[i][0],f[i][1],f[i][2]分别表示使以i为根的原树的子树中删去一些边后合法时,以i为根的当前子树中
1>不含黑色节点
2>含有1或0个白色节点
3>不含有白色节点
再进行状态转移即可

这么好想的dp还实现不好真是醉了>_<

在具体实现时将节点的信息以dfs序存了起来,最后在外边for循环了一遍.
这么2333的方法请吐槽我SB

代码

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
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cstring>

typedef long long ll ;

#define  maxn  300010LL
#define  infi  0x3f3f3f3f3f3f3f3fLL

struct FST { int to , next , len ; } e[maxn<<1] ;
int star[maxn] = {0} , tote = 1 ;
void FST_init() { memset(star , 0 , sizeof star) ; tote = 1 ; }
void AddEdge(int u , int v , int w) {
truee[++tote].to = v ; e[tote].len = w ; e[tote].next = star[u] ; star[u] = tote ;
}

int tot ;
int dfn[maxn] = {0} ;
int data[maxn] = {0} ;
int col[maxn] = {0} ;
int fa[maxn] = {0} ;
ll len[maxn] = {0} ;
ll f[maxn][3] = {0} ;

void dfs(int u , int ff , int l) {
truedfn[u] = ++tot ;
truefa[dfn[u]] = ff , col[dfn[u]] = data[u] , len[dfn[u]] = l ;
trueff = 1 ;
truefor (l=star[u];l;l=e[l].next)
truetrueif (!dfn[e[l].to])
truetruetrueff = 0 , dfs(e[l].to,dfn[u],e[l].len) ;
trueif (ff) {
truetrue/*如果是叶子节点*/
truetrueif (col[dfn[u]] == 0) {
truetruetruef[dfn[u]][0] = infi ;
truetruetruef[dfn[u]][1] = 0LL ;
truetruetruef[dfn[u]][2] = 0LL ;
truetrue} else if (col[dfn[u]] == 1) {
truetruetruef[dfn[u]][0] = 0LL ;
truetruetruef[dfn[u]][1] = 0LL ;
truetruetruef[dfn[u]][2] = infi ;
truetrue} else
truetruetruef[dfn[u]][0] = f[dfn[u]][1] = f[dfn[u]][2] = 0LL ;
true}
}

int main() {
int Time , n , i , u , v , w ;
ll ans , tmp ;
true#define READ
true#ifdef  READ
truetruefreopen("split.in" ,"r",stdin ) ;
truetruefreopen("split.out","w",stdout) ;
true#endif
trueread(Time) ;
truewhile (Time -- >0) {
truetrueFST_init() ;
truetrueread(n) ;
truetrueRep (i,1,n) read(data[i]) ;
truetrueRep (i,2,n) {
truetruetrueread(u) , read(v) , read(w) ;
truetruetrueAddEdge(u,v,w) ;
truetruetrueAddEdge(v,u,w) ;
truetrue}
truetruetot = 0 ;
truetruememset(f,0,sizeof f) ;
truetruememset(dfn,0,sizeof dfn) ;
truetruedfs(1,0,0) ;
truetrueRev (v,n,1) {
truetruetrueu = fa[v] ;
truetruetrueif (col[u] == 0) {
truetruetruetruef[u][0] = infi ;
truetruetruetruetmp = std::min(f[u][1]+f[v][0]+len[v],std::min(f[u][1]+f[v][2],f[u][2]+f[v][1]));
truetruetruetruef[u][1] = std::min(f[u][1]+f[v][1]+len[v],tmp) ;
truetruetruetruef[u][2] += std::min(f[v][2],std::min(f[v][0]+len[v],f[v][1]+len[v])) ;
truetruetrue} else if (col[u] == 1) {
truetruetruetruef[u][0] += std::min(f[v][0],std::min(f[v][1]+len[v],f[v][2]+len[v])) ;
truetruetruetruef[u][1] += std::min(f[v][2],std::min(f[v][0]+len[v],f[v][1]+len[v])) ;
truetruetruetruef[u][2] = infi ;
truetruetrue} else if (col[u] == 2) {
truetruetruetruef[u][0] += std::min(f[v][0],std::min(f[v][1]+len[v],f[v][2]+len[v])) ;
truetruetruetruetmp = std::min(f[u][1]+f[v][0]+len[v],std::min(f[u][1]+f[v][2],f[u][2]+f[v][1]));
truetruetruetruef[u][1] = std::min(f[u][1]+f[v][1]+len[v],tmp) ;
truetruetruetruef[u][2] += std::min(f[v][2],std::min(f[v][0]+len[v],f[v][1]+len[v])) ;
truetruetrue}
truetrue}
truetrueu = 1 ;
truetrueans = std::min(f[u][0],std::min(f[u][1],f[u][2])) ;
truetrueprintf("%lld\n", ans) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章