题目大意：

一棵树上有一个特殊点，特殊点可以影响距离小于等于d的点，现在告诉被影响的点，问特殊点可以在几个点上。

题目分析：

对题意进行转化：求到被影响点的最大距离小于等于d的点数目。

然后就可以进行树型dp，求最大距离需要进行两次dp，第一次子树向父节点传递有用信息，第二字父节点向子树传递有用信息。dp[u][1]表示u距离以该节点为根的子树中的被影响点的最大距离，dp[u][0]表示u距离该子树外的被影响点的最大距离。

\[第一次: dp[u][1] = max\{dp[v][1]\} + 1
\]

\[第二次: dp[v][0] = max(dp[u][0] + 1, max\{dp[u][1\} + 2)
\]

其中第二次中的max{dp[u][1} + 2)如果正是从v转移来的，就取次大值。

初始化如果该节点就是被影响的点那么距离为0，否则为-1。注意当dp之中出现了-1时要进行各种特判。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, d, dp[N][2], ans;

bool mark[N];

vector<int> adj[N];

inline void dfs1(int u, int f){

	int maxDisDown = -1;

	dp[u][1] = mark[u] ? 0 : -1;

	for(int i = adj[u].size()-1; i >= 0; i--){

		int v = adj[u][i];

		if(v == f) continue;

		dfs1(v, u);

		maxDisDown = max(maxDisDown, dp[v][1]);

	}

	if(maxDisDown != -1)

		dp[u][1] = max(dp[u][1], maxDisDown + 1);

}

inline void dfs2(int u, int f){

	int mx1 = -1, mx2 = -1;

	for(int i = adj[u].size()-1; i >= 0; i--){

		int v = adj[u][i];

		if(v == f) continue;

		if(dp[v][1] > mx1){

			mx2 = mx1;

			mx1 = dp[v][1];

		}

		else if(dp[v][1] > mx2){

			mx2 = dp[v][1];

		}

	}

	for(int i = adj[u].size()-1; i >= 0; i--){

		int v = adj[u][i];

		if(v == f) continue;

		int siblingDis = dp[v][1] == mx1 ? mx2 : mx1;

		if(siblingDis != -1)

			siblingDis += 2;

		dp[v][0] = siblingDis;

		if(dp[u][0] != -1)

			dp[v][0] = max(dp[v][0], dp[u][0] + 1);

		if(mark[v])

			dp[v][0] = max(dp[v][0], 0);

		dfs2(v, u);

	}

}

int main(){

//	freopen("h.in", "r", stdin);

	scanf("%d%d%d", &n, &m, &d);

	for(int i = 1; i <= m; i++){

		int x; scanf("%d", &x);

		mark[x] = true;

	}

	for(int i = 1; i < n; i++){

		int x, y; scanf("%d%d", &x, &y);

		adj[x].push_back(y), adj[y].push_back(x);

	}

	dfs1(1, 0);

	dp[1][0] = mark[1] ? 0 : -1;

	dfs2(1, 0);

	for(int i = 1; i <= n; i++)

		ans += dp[i][0] <= d && dp[i][1] <= d ? 1 : 0;

	printf("%d", ans);

	return 0;

}

巴特西

CF337D Book of Evil - 树型dp

题目大意：

题目分析：

code

最新文章

热门文章