首页 > 其他分享 >AT_aising2019_e Attack to a Tree 题解

AT_aising2019_e Attack to a Tree 题解

时间:2024-09-06 14:52:20浏览次数:12  
标签:5010 0x3f int 题解 Tree dfs Attack dp

挺有意思的树型 dp。

思路

发现直接求解很难对限制下手。

但我们可以注意到答案最多为 \(n\)。

考虑将答案记录 dp 状态。

我们可以记 \(dp_{i,j}\) 为子树 \(i\) 合法并且断了 \(j\) 条边的状态。

由于合法状态有两种,并且不好一起考虑,所以可以再在 dp 状态中加一维。

令 \(dp_{i,j,0/1}\) 为子树 \(i\) 内共断了 \(j\) 条边,不是/是全部都为正数的最小和。

转移是简单的,自行推导即可。

时间复杂度:\(O(n^2)\)。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
int s[5010];
int a[5010];
int g[5010][5010][2];
int t[5010][2];
vector<int> to[5010];

inline void dfs(int x, int f) {
  s[x] = 1;
  if (a[x] < 0) g[x][0][0] = a[x];
  if (a[x] > 0) g[x][0][1] = a[x];
  for (auto i : to[x]) {
    if (i == f) continue;
    dfs(i, x);
    memset(t, 0x3f, sizeof t);
    for (int j = 0; j <= s[i]; j++)
      for (int k = 0; k <= s[x]; k++) {
        t[j + k][0] = min(t[j + k][0], g[i][j][0] + g[x][k][0]);
        t[j + k][0] = min(t[j + k][0], g[i][j][1] + g[x][k][0]);
        t[j + k][0] = min(t[j + k][0], g[i][j][0] + g[x][k][1]);
        t[j + k][1] = min(t[j + k][1], g[i][j][1] + g[x][k][1]);
        if (g[i][j][0] < 0 || g[i][j][1] < 1e17) t[j + k + 1][0] = min(t[j + k + 1][0], g[x][k][0]);
        if (g[i][j][0] < 0 || g[i][j][1] < 1e17) t[j + k + 1][1] = min(t[j + k + 1][1], g[x][k][1]);
      }
    s[x] += s[i];
    memcpy(g[x], t, sizeof t);
  }
}

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 2; i <= n; i++) {
    int u, v;
    cin >> u >> v;
    to[u].push_back(v);
    to[v].push_back(u);
  }
  memset(g, 0x3f, sizeof g);
  dfs(1, 0);
  for (int i = 0; i <= n; i++) {
    if (g[1][i][0] < 0 || g[1][i][1] < 1e17) {
      cout << i << "\n";
      return 0;
    }
  }
}

标签:5010,0x3f,int,题解,Tree,dfs,Attack,dp
From: https://www.cnblogs.com/JiaY19/p/18400233

相关文章

  • P8139 [ICPC2020 WF] Sweep Stakes 题解
    思路容易发现,题目要求我们动态维护这样一个多项式。\[\prod_{i}(1-p_i+p_ix)\]如何维护。由于精度问题,我们很难去进行一个多项式除法将其暴力求出。考虑\(p_i\le0.2\)。可以得知,我们的多项式的数的增减是比较大的。那么在一定数量后,一些可能有值的系数在当前精度下是可以......
  • ORCLE数据库语言设置原因查询不出数据的问题解决
    问题现象:oracle数据库视图中存在数据,但是jdbc查询视图查询不出来,后发现视图中有根据默认语言的过滤,如下图: 客户端查询环境语言为 web服务器查询环境语言为US,所以数据查询不出来。解决方案:修改应用端的NLS_LANG的配置与SQL保持一致linux执行下面代码exportNLS_LANG="......
  • CF1469D Ceil Divisions题解
    CF1469DCeilDivisions感觉是很巧妙的一题?一开始想到,对于任何小于$n$的数$x$,直接对它除以$n$可以得到$1$。那么对$3\simn-1$做完此操作后,还剩下$1$、$2$、$n$。将$n$变成$1$要花费$logn$次,显然总操作次数超过了$n+5$次。进一步地,发现瓶颈在于把$n$变成$1$,于是利用根号,用$\sqr......
  • zTree树形菜单交互选项卡效果实现
    1、添加自定义属性page 2、为ztree每个树形节点,添加点击事件1<!DOCTYPEhtml>2<html>34<head>5<metacharset="UTF-8">6<title>ztree树形菜单的使用</title>7<!--导入jquery核心类库-->8......
  • 9.6 上午 becoder 模拟赛总结&题解
    T1语言水题不多说,很容易发现NP需要满足的只是最后一个单词为N,前面是A或N都可以随意放。所以用两个数组,\(v1_i\)记录以\(i\)结尾的前缀是否可以构成NP,\(v2_i\)记录以\(i\)为开头的后缀是否可以构成NP。最后for循环扫一遍是否有同时满足\(v1_{i-1}=true\)和......
  • CF381B题解
    我们先理解题意,大致意思是:给你一个序列让你组成一个中间有一个数,左侧递增右侧递减的数列。从这道题的题意来看,大概思路是:1.我们要将最大值设为中间的数,然后左右两端尽可能的小。2.跑两遍循环,分别为左边的递增边的递减。3.还有,因为一个数可以出现很多次,我们需要一个vis......
  • 2024 年高教社杯全国大学生数学建模竞赛B题解题思路(第一版)
    原文链接:https://www.cnblogs.com/qimoxuan/articles/18399372赛题:问题1:抽样检测方案设计分析:抽样检测方案需要在保证决策准确性的同时,尽量减少检测成本。需要考虑抽样误差对决策的影响,以及如何设置抽样大小和接受/拒绝标准。解题思路:1.确定抽样方法:采用属性抽样,......
  • 【洛谷 P1449】后缀表达式 题解(栈+分支)
    后缀表达式题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:对应的后缀表达式为:。在该式中,@为表达式的结束符号。.为操作数的结束符号。输入格式输入一行......
  • CodeForces 2009G Yunli's Subarray Queries 题解
    云璃!高质量Div.4,吊打某些Div.2Only/Edu/Div.3。本题是下面四道题目的有机结合,优雅且经典。LuoguP4168[Violet]蒲公英|LuoguP1997faebdc的烦恼|LuoguP3203[HNOI2010]弹飞绵羊|LuoguP3246[HNOI2016]序列建议先完成这四题。(必须指出:用蒲公英的分块方......
  • P3688 [ZJOI2017] 树状数组 题解
    P3688[ZJOI2017]树状数组题解记录一下做这道题的心路历程,说明在没有事先知道“九条是求成了后缀和”的情况下如何发现,以及解释一些部分分的做法。sub1,18pts:暴力搜索无脑枚举,复杂度\(\mathcalO(n^m)\)。代码:#include<bits/stdc++.h>#defineintlonglong#defineloop......