B Parades

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

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

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

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

#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$ 的度数加一。

画张图吧：

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

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