【树形dp】【CF161D】distance on a tree + 【P1352】没有上司的舞会

T1题面：

　输入点数为N一棵树

　求树上长度恰好为K的路径个数

　(n < 1e5, k < 500)

　　这是今天的考试题，也是一道假的紫题，因为我一个根本不会dp的蒟蒻只知道状态就一遍A掉了……（然后我当时不会……emm）

　　考虑f[i][j]表示点i为根的子树中深度为j的点的个数，初始设置f[i][0] = 1。转移的时候，每搞完一棵子树就用这棵子树内的数据用乘法原理更新ans，然后再把它的贡献累加给根，这样可以保证统计不重不漏。

　　也可以用点分治来做。

代码：

#include <iostream>
#include <cstdio>
#define maxn 50010
using namespace std;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
void open_file(string s) {
string In = s + ".in", Out = s + ".out";
freopen(In.c_str(), "r", stdin);
freopen(Out.c_str(), "w", stdout);
}
int head[maxn], top, n, k;
struct E {
int to, nxt;
} edge[maxn << 1];
inline void insert(int u, int v) {
edge[++top] = (E) {v, head[u]};
head[u] = top;
}
int f[maxn][510];//第二维j表示深度为j的点数
long long ans;
void dp(int u, int pre) {
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == pre)
continue;
dp(v, u);
for (int i = 0; i < k; ++i) //先统计答案
ans += f[u][i] * f[v][k-i-1];
for (int i = 1; i <= k; ++i) //算贡献
f[u][i] += f[v][i-1];
}
return;
}
int main() {
// open_file("distance");
read(n), read(k);
int u, v;
for (int i = 1; i < n; ++i) {
read(u), read(v);
insert(u, v), insert(v, u);
}
for (int i = 1; i <= n; ++i)
f[i][0] = 1;
dp(1, 0);
printf("%I64d\n", ans);
return 0;
}

　　T2题面就不放了。这是一道树形dp的入门题。

　　考虑每个点可以有选与不选两种状态，设f[i][0]表示不选这个点后以该点为根的最大贡献，f[i][1]表示选。我们可以自底向顶转移，有f[u][1] = w[u] + sigma(f[v][0])，f[u][0] = sigma(max(f[v][0], f[v][1])。注意第二个方程中选不选子节点是都可以的，要注意这种比较松的限制可能遗漏。

代码：

#include <iostream>
#include <cstdio>
#define maxn 6010
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
using namespace std;
int head[maxn], top;
struct E {
int to, nxt;
} edge[maxn << 1];
inline void insert(int u, int v) {
edge[++top] = (E) {v, head[u]};
head[u] = top;
}
int f[maxn][2], w[maxn], ind[maxn], n, root;
void dp(int u) {
f[u][1] = w[u];
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
dp(v);
f[u][1] += f[v][0];
f[u][0] += max(f[v][1], f[v][0]);
}
return;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i)
read(w[i]);
int u, v;
for (int i = 1; i < n; ++i) {
read(u), read(v);
insert(v, u);
++ind[u];
}
for (int i = 1; i <= n; ++i)
if (!ind[i]) {
root = i;
break;
}
dp(root);
printf("%d", max(f[root][0], f[root][1]));
return 0;
}

巴特西

【树形dp】【CF161D】distance on a tree + 【P1352】没有上司的舞会

最新文章

热门文章