Rockdu's Blog

题目描述

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点，编号为0,1,2 … , V− 1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 0 出发，移动 N 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

输入输出格式

输入格式：

第一行包含2个正整数V, N，其中 V 表示格点总数，N 表示移动步数。

接下来V − 1行，每行两个数ai​,bi​，表示编号为ai​,bi​的两个格点之间有连线。

输出格式：

输出一行一个整数，表示最多经过的格点数量。

输入输出样例

5 2
1 0
2 1
3 2
4 3

3

9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5

5

说明

【输入输出样例 1 说明】

从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

【输入输出样例 2 说明】

一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7，经过 0, 1, 3, 5, 7 这 5 个格点。

【数据规模与约定】

对于 100%的测试点，N,V ≤ 100, 0 ≤a_i,b_i< V

楼下dalao观察的性质真的十分巧妙

蒟蒻的我根本没有想到这些性质

既然大家的做法都这么优雅，那么我来写一个莽夫做法吧 考虑处理树上路径的一种套路 我们记f(u,j)表示从u往子树中走j步回到u的最多经过点数 记g(u,j)表示从u往子树中走j步不一定回到u的最多经过点数 考虑f(u,j)可以用所有儿子的f数组合并而来，合并过程类似背包。

但是g(u,j)怎么计算呢？

发现如果不一定回到u的话我们的路径一定长成这个样子：在一些子树中(包括空子树)绕了回来，并且在这些子树之外的某棵子树走了下去。 假设最后从v走了下去。由于不可以从v绕一圈再从v走下去，我们需要得到除了v子树以外，其他子树合并后的f数组。 考虑对每一层dp数组做前缀和、后缀和操作。

具体的来说，我们把儿子合并到根的子问题看成一个序列问题，把儿子依次排布看成序列。那么我们如果对于每一个i预处理出它前缀合并成的f数组和后缀合并成的f数组，就可以把刨开v子树转化成合并一个前缀和一个后缀。

这道题就可以通过了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
struct edge {
    int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
int n, k, u, v, f[maxn][maxn];
int Lf[maxn][maxn], Rf[maxn][maxn], g[maxn][maxn];
int L[maxn], R[maxn], lst[maxn], tmp[maxn][maxn];
void merge(int a[maxn], int b[maxn]) {
    for(register int j = k; j >= 2; --j) {
        for(register int l = j - 2; l >= 0; --l)
            a[j] = max(a[j], a[j - l - 2] + b[l]);
    }
}
void DPpref(int u) {
    int now = lst[u];
    if(now == -1) return;
    while(~L[now]) merge(Rf[L[now]], Rf[now]), now = L[now];
    while(~R[now]) merge(Lf[R[now]], Lf[now]), now = R[now];
}
void DPF(int u, int p) {
    int last = -1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        if(~last) 
            lst[u] = v, L[v] = last, R[last] = v;
        last = v, DPF(v, u);
        merge(f[u], f[v]);
        memcpy(Rf[v], f[v], sizeof(f[v]));
        memcpy(Lf[v], f[v], sizeof(f[v]));
    }
    DPpref(u);
    for(register int j = k; j >= 0; --j)
        if(f[u][j]) ++f[u][j];
    f[u][0] = 1;
}

void DPG(int u, int p) {
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        DPG(v, u);
        if(~L[v]) merge(tmp[v], Lf[L[v]]);
        if(~R[v]) merge(tmp[v], Rf[R[v]]);
        for(register int j = k; j >= 1; --j) {
            for(register int l = j - 1; l >= 0; --l)
                tmp[v][j] = max(tmp[v][j], tmp[v][j - l - 1] + g[v][l]);
            g[u][j] = max(g[u][j], tmp[v][j]);
        }
    }
    for(register int j = k; j >= 0; --j)
        if(g[u][j]) ++g[u][j];
    g[u][0] = 1;
}

int main() {
    memset(L, -1, sizeof(L));
    memset(R, -1, sizeof(R));
    memset(lst, -1, sizeof(lst));
    scanf("%d%d", &n, &k);
    for(register int i = 1; i < n; ++i)
        scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
    DPF(0, -1); 
    DPG(0, -1);
    printf("%d", g[0][k]);
    return 0;
}