T1 Anniversary party/没有上司的舞会

【题意】

公司要开party，如果一个员工的上司来了，那么那个员工就不会来。
每个人都有一个开心值，要求到场的员工的开心值之和最大。

【思路】

设 $f[u,1/0]$ 为员工 $u$ 来或者不来的最大开心值和。

当员工 $u$ ，那他的下属 $u$ 就一定不来
f [ u , 1 ] = min ⁡ { f [ v , 0 ] } + h a p p y [ u ] f[u,1] = \min \{ f[v,0]\} + happy[u] f[u,1]=min{f[v,0]}+happy[u]
当员工 $u$ 不来，那他的下属 $u$ 可来可不来，
f [ u , 0 ] = min ⁡ { f [ v , 0 ] , f [ v , 1 ] } f[u,0] = \min \{f[v,0], f[v, 1]\} f[u,0]=min{f[v,0],f[v,1]}

点击查看代码

#include 
using namespace std;

const int N=6005;
int happy[N];
vector<int> mp[N];
int n;
int fa[N];
int f[N]; // u来
int g[N]; // u不来

void dp(int u)
{
	for(int i=0; i<mp[u].size(); i++)
	{
		int v=mp[u][i];
		dp(v);
		g[u]+=max(g[v],f[v]);
		f[u]+=g[v];
	}
	f[u]+=happy[u];
}

int main()
{
	while(cin>>n)
	{
		memset(f,0,sizeof f);
		memset(g,0,sizeof g);
		memset(fa,0,sizeof fa);

		for(int i=1; i<=n; i++) cin>>happy[i];
		for(int i=0; i<N; i++) mp[i].clear();
		for(int i=1; i<=n; i++)
		{
			int l,k;
			cin>>l>>k;
			if(l == 0 && k == 0) break;
			mp[k].push_back(l);
			fa[l]=k;
		}

		for(int i=1; i<=n; i++)
			if(fa[i]==0)
			{
				dp(i);
				cout<<max(g[i],f[i])<<endl;
				break;
			}
	}

	return 0;
}
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

T2 Rebuilding Roads

【题意】

给出一棵含有 n 个节点的有根树，我们现在希望通过删除一些边，让他有一棵有 m 个节点的新树，求删除的最少边的数量。$(1\le p\le n\le 150)$

【思路】

定义 $f[u,k]$ 为 $n$ 的子树删剩 $k$ 个点的最小代价。
考虑树上背包，每一个点只能选一次，类似于01背包。
f [ u , k ] = min ⁡ j = 1 j ≤ k { f [ v , j ] + f [ u , k − j ] } f[u,k] = \min^{j \le k}_{j=1} \{ f[v,j] + f[u,k-j] \} f[u,k]=j=1minj≤k​{f[v,j]+f[u,k−j]}
由于是01背包，所以需要枚举 $j$ 的时候要倒序。
最后答案为 $$ans=\underset{i=1}{\overset{i\le n}{\min }}f[i,p]+[i!=1]$$。

T3 Cell Phone Network

【题意】

有一些农场构成了一棵树，在一个点建立信号塔后，所有相邻的点都可以收到信号。
现在要求所有的点都有信号，求最小建多少个信号塔。

【思路】

定义 $f[u,0/1/2]$ 为 $u$ 的子树中所有点都有信号且 $u$ 是被自己 $(0)$，儿子 $(1)$，还是父亲 $(2)$ 覆盖的时建的最小的信号塔个数。

f [ u , 0 ] = ∑ v ∈ s o n ( u ) min ⁡ { f [ v , 0 ] , f [ v , 1 ] , f [ v , 2 ] } f[u,0] = \sum_{v \in son(u)} \min \{ f[v,0], f[v,1], f[v,2]\} f[u,0]=v∈son(u)∑​min{f[v,0],f[v,1],f[v,2]}

f [ u , 1 ] = ∑ v ∈ s o n ( u ) min ⁡ { f [ v , 0 ] , f [ v , 1 ] } + [ ∃ v ∈ s o n ( u ) , f [ v , 0 ] < f [ v , 1 ] ] f[u,1] = \sum_{v \in son(u)} \min \{ f[v,0], f[v,1]\} + [\exists v \in son(u),f[v,0] < f[v,1]] f[u,1]=v∈son(u)∑​min{f[v,0],f[v,1]}+[∃v∈son(u),f[v,0]<f[v,1]]

f [ u , 2 ] = ∑ v ∈ s o n ( u ) min ⁡ { f [ v , 0 ] , f [ v , 1 ] } f[u,2] = \sum_{v \in son(u)} \min \{ f[v,0], f[v,1]\} f[u,2]=v∈son(u)∑​min{f[v,0],f[v,1]}

答案为 $\min (f[u,0],f[u,1])$，因为根没有父亲来给它提供信号。

点击查看代码

#include 
#include 
#include 
#include 
using namespace std;

const int N = 10005;

struct Edge
{
	int v,nxt;
} e[N*2];
int head[N], idx;
void add(int u,int v)
{
	e[++idx].v = v,e[idx].nxt = head[u], head[u] = idx;
}
int n;

int f[N][3];
void dfs(int u,int fa)
{
	f[u][0] = 1;
	bool flag = 1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v = e[i].v;
		if(v == fa) continue;
		dfs(v,u);
		f[u][2] += min(f[v][0],f[v][1]);
		f[u][0] += min(f[v][0], min(f[v][1], f[v][2]));
		
		if(f[v][0] <= f[v][1]) flag = 0, f[u][1] += f[v][0];
		else f[u][1] += f[v][1];
	}
	f[u][1] += flag;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) 
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v); add(v,u);
	}
	
	dfs(1, 0);
	
	cout<<min(f[1][0],f[1][1]);
	
	return 0;
} 
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

T4 Tree Cutting

【题意】

找到一个点 $u$，使得删去 $u$ 之后，最大联通块的大小小于总点数的一半。

【思路】

求树的重心，树的重心定义为如果存在一个点 $u$ ，当去掉点 $u$ 后，树的各个连通块中，节点数最多的连通块的节点数最小。注意树可能存在多个重心。

判断点 $u$ 的子树大小是否大于 $\frac{n}{2}$，如果是，则再判断一下它的儿子中是否有需要删掉的，如果删了儿子，就不需要删它本身了。

点击查看代码

#include 
#include 
#include 
#include 
using namespace std;

const int N = 10005, INF = 0x3f3f3f3f;

int n;
struct Edge
{
	int v, nxt;
} e[N*2];
int head[N], idx;
int father[N];
void add(int u,int v)
{
	e[++idx].v = v, e[idx].nxt = head[u], head[u] = idx;
}

vector<int> ans;
int f[N];
void dfs(int u,int fa)
{
	bool flag = 1;
	f[u] = 1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v = e[i].v;
		if(v == fa) continue;
		
		dfs(v,u);
		
		f[u] += f[v];
		if(f[v] > n/2) flag = 0;
	}
	if(f[u] < n / 2) flag = 0;
	if(flag) ans.push_back(u);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		father[v] = u;
		add(u,v), add(v,u);
	}
	
	dfs(1,0);
	
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
	
	return 0;
}
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

T5 Zero Tree

【题意】

选择一个包含根的子树，一次操作中可以将其所有点同时 $+1$ 或 $-1$。
求将所有点值变为 $0$ 需要的最少次数。

【思路】

定义 $f[u,0/1]$ 将 $u$ 的子树减/加成 $0$ 需要的最少次数。
由于可以随便选哪几个子树，所以至少加上子树中的最小的负数值，减去子树中最小的正数值。

初始化：如果 $a_i<0$，则 $f[i,1]=|a_i|$，否则 $f[u,0]=a_i$。

转移方程：
$$f[u,0]=\underset{v\in son(u)}{\max }f[v,0]$$
$$f[u,1]=\underset{v\in son(u)}{\max }f[v,1]$$

点击查看代码

#include 
using namespace std;

typedef long long LL;
const LL N = 1e5 + 10;

LL n; 
struct Edge
{
	LL v,nxt;
} e[N*2];
LL head[N], idx;
void add(LL u,LL v)
{
	e[++idx].v = v,  e[idx].nxt = head[u], head[u] = idx;
}

LL a[N];
LL f[N], g[N];
void dfs(LL u,LL fa)
{
	for(LL i=head[u];i;i=e[i].nxt)
	{
		LL v = e[i].v;
		if(v == fa) continue;
		
		dfs(v,u);
		f[u] = max(f[u],f[v]);
		g[u] = max(g[u],g[v]);
	}
	a[u] += f[u] - g[u];
	if(a[u] > 0) g[u] += a[u];
	else f[u] -= a[u];
}

int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<n;i++) 
	{
		LL u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v),add(v,u);
	}
	for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);
	
	dfs(1,0);
	
	cout<<f[1] + g[1];
	
	return 0;
}
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

T6 Distance in Tree

【题意

给出一棵有 $n$ 个点的树，求树上距离恰好为 $k$ 的点对的数量，距离定义为两点之间简单路径上的边的数目。

注意 $(u,v)$ 和 $(v,u)$ 只能算一个。

【思路】

我们钦定点 $1$ 为根将这个树拉起来。

发现一个点 $u$，向下找距离为 $k$ 的点非常好做，但向上找就比较麻烦。

我们定义 $f[u,j]$ 为点 $u$ 向下距离为 $j$ 的点的个数。

明显，点 $u$ 向下距离为 $j$ 的点的个数可以从到点 $u$ 的儿子距离为 $j-1$ 的点转移过来。

可得第一个方程： $$f[u,j]=\sum _{v\in son(u)}f[v,j-1]$$

但是也会出现下图这种情况：

此时点 $u$ 为两个点的 $lca$，且 $u$ 到两点的距离之和恰好为 $k$。

对于这种情况，我们只要找到一个 $u$ 子树中的点 $v_1$，使其到点 $u$ 的距离为 $j$，另一个 $u$ 子树中的点 $v_2$，使其到点 $u$ 的距离为 $k-j$，就可以找到一对距离为 $k$ 的点对了。

如何统计这种情况的方案数呢？

我们可以考虑乘法原理，将 $u$ 子树中，到 $u$ 距离为 $j$ 的点数乘上在 $u$ 子树中到 $u$ 距离为 $k-j$ 的点数即可。

最终答案为： $$ans=\sum _{u\in V}\sum _{j=0}^{j<k}f[u,j]\times f[u,j-k]$$

点击查看代码

#include 
using namespace std;

typedef long long LL;
const int N = 50005, K = 505;

int n, k;
int f[N][K], g[N][K];

struct Edge
{
	int v,nxt;
} e[N*2];
int head[N], idx;
void add(int u,int v)
{
	e[++idx].v = v, e[idx].nxt = head[u], head[u] = idx;
}

LL ans = 0;
void dfs(int u,int fa)
{
	f[u][0] = 1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v = e[i].v;
		if(v == fa) continue;
		dfs(v,u);
		for(int j=0;j<k;j++) ans += f[u][j] * f[v][k-j-1];
		for(int j=1;j<=k;j++) f[u][j] += f[v][j-1];
	}
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++) 
	{
		int u, v;
		scanf("%d%d",&u,&v);
		add(u,v), add(v,u);
	}
	
	dfs(1,0);
			
	cout<<ans;
	
	return 0;
}
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