比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18834991
开题 + 补题情况
这场就非常的难了，感觉有打区域赛的感觉了，开了两题，一个签到一个树形 DP，前面有个线段树的题写了个二分 + 线段树，不出意料地 TLE 了。
1008 - 木柜子组乐队
考虑用键盘手和不用键盘手，分别计算，很简单的组合数学。
点击查看代码
void solve()
{
i64 a, b, c, d, e;std::cin >> a >> b >> c >> d >> e;
i64 ans = 0;
ans += a * b * c * d * e;
ans += a * b * c * d * (d - 1) / 2;
std::cout << ans>1007 - 森林迷宫
一开始铸币了还在找两个点的 LCA 加换根。
这个题，只需要把起点或终点作为树的根，然后从深的那个点起，往上一层一层爬树，同时收集其他枝干的答案（只要往这个枝干走是正的，就说明对答案有贡献，走就一定是优的），每个枝干的答案只需要简单地进行树形 DP 就行，对于结点 \(i\) 的出了走过的那个结点之外的结点 \(j\)，\(dp_i = \max(dp_i, dp_i + dp_j + p + q)\)。
赛时代码写了依托答辩。
点击查看代码
#include
#define inf32 1e9
#define inf64 2e18
#define ls o << 1 xss=removed xss=removed xss=removed xss=removed>> n;
std::vector> e(n + 1);
for(int i = 1;i < n>> u >> v >> p >> q;
e[u].push_back({v, p, q});
e[v].push_back({u, q, p});
}
std::vector> g(n + 1);
std::vector fa(n + 1);
std::vector dep(n + 1);
int s, t;std::cin >> s >> t;
auto dfs = [&](auto &&self, int st, int pre, i64 w) -> void {
dep[st] = dep[pre] + 1;
for(auto &i : e[st]) {
if(i.v == pre)continue;
g[st].push_back({i.v, i.p});
fa[i.v] = {st, i.p, i.q};
self(self, i.v, st, i.q);
}
};
dfs(dfs, s, 0, 0);
std::vector dp(n + 1);
auto dfs1 = [&](auto &&self, int st) -> void {
dp[st] = 0;
for(auto &[v, w] : g[st]) {
self(self, v);
dp[st] = std::max(dp[st], dp[st] + dp[v] + fa[v].p + fa[v].q);
}
};
dfs1(dfs1, s);
auto lca = [&](int x, int y) -> int {
while(x != y) {
if(dep[x] < dep xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed> 0) {
ans -= dp[pre] + fa[pre].p + fa[pre].q;
}
}
ans += fa[s].q;
pre = s;
s = fa[s].v;
}
int pres = pre;
pre = 0;
while(t != lc) {
ans += dp[t];
if(pre != 0) {
if(dp[pre] + fa[pre].p + fa[pre].q > 0) {
ans -= dp[pre] + fa[pre].p + fa[pre].q;
}
}
ans += fa[t].p;
pre = t;
t = fa[t].v;
}
int pret = pre;
int hi = fa[lc].v;
if(hi != 0) {
i64 oh = dp[hi];
if(dp[lc] + fa[lc].p + fa[lc].q > 0) {
oh -= dp[lc] + fa[lc].p + fa[lc].q;
}
ans = std::max(ans, ans + oh + fa[lc].p + fa[lc].q);
}
i64 tmp = dp[lc];
if(pres != 0) {
if(dp[pres] + fa[pres].p + fa[pres].q > 0) {
tmp -= dp[pres] + fa[pres].p + fa[pres].q;
}
}
if(pret != 0) {
if(dp[pret] + fa[pret].p + fa[pret].q > 0) {
tmp -= dp[pret] + fa[pret].p + fa[pret].q;
}
}
ans = std::max(ans, ans + tmp);
std::cout << ans xss=removed>> t;
while(t --)solve();
return 0;
}
/*
What you want is what you love, so fight for it!
*/
