做网站的价钱,django 电商网站开发,上海三凯建设管理咨询有限公司网站,公司网站二维码怎么做的BZOJ 4813 虽然数据范围很迷人#xff0c;但是想树形$dp$没有前途。 先发现一个事情#xff0c;就是我们可以先选择一条链#xff0c;最后要走到这一条链上不回来#xff0c;走到链上的点每一个只需要一步#xff0c;而如果要走这条链之外的点#xff0c;一个点需要走两步…BZOJ 4813 虽然数据范围很迷人但是想树形$dp$没有前途。 先发现一个事情就是我们可以先选择一条链最后要走到这一条链上不回来走到链上的点每一个只需要一步而如果要走这条链之外的点一个点需要走两步。 这条链怎么选取为了尽量减少步数肯定是最长链。 现在有了一个显然的事情如果限制步数$stp$不比最长链长度$mx$大的话那么直接在最长链上走一走就好了答案为$stp 1$。 一棵树最少需要$mx 2 * (n - mx - 1) 2n - mx - 2$步走完如果$stp$不小于这个值那么一定能走完答案为$n$。 剩下的情况只要先考虑走完最长链然后尽量分配步数到别的点上去就好了答案为$mx 1 \left \lfloor \frac{stp - mx}{2} \right \rfloor$。 时间复杂度$O(n)$。 应该也有$dp$的办法吧。 Code #include cstdio
#include cstring
using namespace std;const int N 105;int n, stp, tot 0, head[N], dep[N];struct Edge {int to, nxt;
} e[N 1];inline void add(int from, int to) {e[tot].to to;e[tot].nxt head[from];head[from] tot;
}inline void read(int X) {X 0; char ch 0; int op 1;for(; ch 9 || ch 0; ch getchar())if(ch -) op -1;for(; ch 0 ch 9; ch getchar())X (X 3) (X 1) ch - 48;X * op;
}inline void chkMax(int x, int y) {if(y x) x y;
}void dfs(int x, int fat, int depth) {dep[x] depth;for(int i head[x]; i; i e[i].nxt) {int y e[i].to;if(y fat) continue;dfs(y, x, depth 1);}
}int main() {read(n), read(stp);for(int x, y, i 1; i n; i) {read(x), read(y);x, y;add(x, y), add(y, x);}dfs(1, 0, 1);int mx 0;for(int i 1; i n; i)chkMax(mx, dep[i] - 1);if(stp mx) return printf(%d\n, stp 1), 0;if(stp 2 * n - mx - 2) return printf(%d\n, n), 0;printf(%d\n, mx 1 (stp - mx) / 2);return 0;
} View Code 转载于:https://www.cnblogs.com/CzxingcHen/p/9852755.html
