4.28 写题

B Parades

这题有一个关键的性质:可以发现一定有一种全局最优解满足每个点都是局部最优解。具体来说,由于每个点向上只有一条边,所以即使你在这个点子树的时候放弃选择一条路径,也只能最多获得 $1$ 的贡献,还不如直接选择子树之内。(感觉这种性质在权值全 $1$ 的时候都可以尝试一下有没有)

于是我们设 $dp[u]$ 表示 $u$ 子树最多可以选多少个路径,再对每个子树维护出一个集合,这个集合中的点满足存在一个选择最多路径的方案,使得这个点没有被覆盖。

考虑转移,由于 $n \le 10^3$ 且度数很小,我们可以在每个点做一个状压,转移出当连向某些儿子的边被选择时,最多可以选择多少个路径(感觉可能这个东西也是可以流的)。然后把所有取到最大值的状态取个交,得到的集合就是如果想要获得最大值就必须放弃的子树,剩下的子树都是存在方案使得不被覆盖的,由于最多只会选一条路径连上去,所以这么做是对的。

复杂度 $O(\frac{n^2}{\omega} + nd^22^d)$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "bitset"
#include "cassert"
using namespace std;
#define MAXN 1036
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;

void ckm( int& a , int b ) {
a = max( a , b );
}

int n , m;

vi G[MAXN];
int g[MAXN][19] , dep[MAXN];
void afs( int u , int f ) {
dep[u] = dep[f] + 1;
for( int v : G[u] ) if( v != f ) {
g[v][0] = u;
rep( k , 1 , 16 ) if( g[g[v][k - 1]][k - 1] ) g[v][k] = g[g[v][k - 1]][k - 1]; else break;
afs( v , u );
}
}

int lca( int u , int v ) {
if( dep[u] < dep[v] ) swap( u , v );
if( dep[u] != dep[v] ) per( k , 16 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
if( u == v ) return u;
per( k , 16 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
return g[u][0];
}

vi ol[MAXN];
vector<pii> rd[MAXN];

int sd[1 << 10 | 4] , dp[MAXN];
bitset<MAXN> S[MAXN];
void dfs( int u , int f ) {
int dd[11][11];
mem( dd );
int cc = -1;
for( int v : G[u] ) {
++ cc;
if( v == f ) continue;
dfs( v , u );
dp[u] += dp[v];
for( auto t : ol[u] ) if( S[v][t] )
dd[cc][cc] = 1;
for( auto& t : rd[u] ) {
if( t.fi < 0 && S[v][-t.fi] ) t.fi = cc;
if( t.se < 0 && S[v][-t.se] ) t.se = cc;
}

}
int s = G[u].size();
for( auto t : rd[u] ) if( t.fi >= 0 && t.se >= 0 ) dd[t.fi][t.se] = dd[t.se][t.fi] = 1;
mem( sd );
int mx = 0;
rep( st , 0 , ( 1 << s ) - 1 ) {
rep( f , 0 , s - 1 ) if( ~st & ( 1 << f ) ) {
if( st != ( 1 << s ) - 1 ) {
if( dd[f][f] ) ckm( sd[st | ( 1 << f )] , sd[st] + 1 );
rep( k , 0 , s - 1 ) if( !( st & ( 1 << k ) ) && dd[f][k] ) ckm( sd[st | ( 1 << f ) | ( 1 << k )] , sd[st] + 1 );
}
}
mx = max( mx , sd[st] );
}
dp[u] += mx;
int ts = ( 1 << s ) - 1;
rep( i , 0 , ( 1 << s ) - 1 ) if( sd[i] == mx ) ts &= i;

S[u][u] = 1;
rep( i , 0 , G[u].size() - 1 ) {
int v = G[u][i];
if( v == f ) continue;
if( ~ts & ( 1 << i ) ) S[u] |= S[v];
}
}

int tes;

void solve() {
++ tes;
cin >> n;
rep( i , 1 , n ) G[i].clear() , ol[i].clear() , rd[i].clear() , dp[i] = 0 , mem( g[i] );
rep( i , 1 , n ) rep( j , 1 , n ) S[i][j] = 0;
rep( i , 2 , n ) {
int u , v;
scanf("%d%d",&u,&v);
G[u].pb( v ) , G[v].pb( u );
}
afs( 1 , 1 );
cin >> m;
rep( i , 1 , m ) {
int u , v;
scanf("%d%d",&u,&v);
int l = lca( u , v );
if( l == u ) ol[u].pb( v );
else if( l == v ) ol[v].pb( u );
else rd[l].eb( -u , -v );
}
dfs( 1 , 1 );
cout << dp[1] << endl;
}

signed main() {
// freopen("1.in","r",stdin);
int T;cin >> T;while( T-- ) solve();
// solve();
}

C Fox And Polygon

有意思的题。我们考虑给最开始的形状变成 $1$ 连向所有点,然后从这个形状转化成最后的形状。

具体操作可以枚举一个与 $1$ 无直接连边的点,然后找到它左右第一个与 $1$ 有连边的点(显然 $1$ 两边的点就与 $1$ 有边,所以不会跨过 $1$ ),然后由于所有剖成的图形都是三角形,这两个点之间必然有边,我们来翻转这条边。根据这个题对操作的定义,这条边一定会使得 $1$ 的度数加一。

画张图吧:

image.png

在实际操作中可能一次操作后这条边并没有变成 $1-u$ ,所以要一直这么做知道 $u$ 与 $1$ 已经有连边。

这样操作次数是 $O(n)$ 的,并且严格小于 $2n$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/04/28/428-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog