首页 > 其他分享 >LOJ #6175. 「美团 CodeM 初赛 Round B」黑白树

LOJ #6175. 「美团 CodeM 初赛 Round B」黑白树

时间:2022-10-25 11:37:22浏览次数:87  
标签:fr LOJ 美团 maxx 初赛 int num head 节点


题目链接:​​传送门​

一个很贪心的数位dp
显然从叶节点开始染色是优的
因为相比更靠上的节点来说会染到更多的节点
那就先去染叶节点,在他的父亲节点处判断是否被覆盖
如果父亲不能被覆盖那就ans++,否则更新父亲节点能覆盖到的最远点

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
struct node {int next, to;}e[A];
int head[A], num;
void add(int fr, int to) {e[++num].next = head[fr]; e[num].to = to; head[fr] = num;}
int n, fa[A], k[A], ans;
int dfs(int fr) {
int maxx = 0;
for (int i = head[fr]; i; i = e[i].next) {
int ca = e[i].to;
if (ca == fa[fr]) continue;
maxx = max(maxx, dfs(ca));
}
if (maxx <= 1) {ans++; return k[fr];}
k[fa[fr]] = max(k[fa[fr]], k[fr] - 1);
return maxx - 1;
}

int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), add(i, fa[i]), add(fa[i], i);
for (int i = 1; i <= n; i++) scanf("%d", &k[i]);
dfs(1); cout << ans << endl;
}


标签:fr,LOJ,美团,maxx,初赛,int,num,head,节点
From: https://blog.51cto.com/lyle/5794325

相关文章

  • LOJ #10005. 「一本通 1.1 练习 1」数列极差
    题目链接:​​传送门​​贪心题才是难的按照从小到大的顺序排,这样相乘会得到最大值,因为后面的最大值乘的更多最小值同理,就是从大到小处理就可以但是注意在操作的过程中不......
  • LOJ #3011. 「JOI 2019 Final」画展
    题目链接:​​传送门​​用最大的画框配最大的画显然是最优的那么挨个匹配就行#include<bits/stdc++.h>#defineusingnamespacestd;typedeflonglongll;pair<int,int>......
  • LOJ #2012. 「SCOI2016」背单词
    题目链接:​​传送门​​显然第一个情况和第二个情况不如第三个更优并且他们可以避免,所以尽量构造第三种情况将每个字符倒着插入trie树,因为先放后面的字符串是更优的然后......
  • LOJ #6208. 树上询问
    题目链接:​​传送门​​线段树维护每个点的k,t,d当做懒标记来维护这就需要对懒标记的理解了#include<bits/stdc++.h>#defineusingnamespacestd;typedeflonglongll;......
  • LOJ #6220. sum
    题目链接:​​传送门​​官方题解:有一个结论:必有连续的一串数和为n的倍数证明:先求个前缀和若这个前缀和中有的倍数,则这个前缀即为答案若这个前缀和中没有的倍数,即模余~......
  • LOJ #10202. 「一本通 6.2 练习 5」樱花
    题目链接:​​传送门​​​​别人的题解​​​不想写那么多latex了化完式子之后就是求的约数个数#include<bits/stdc++.h>#defineusingnamespacestd;typedeflonglong......
  • loj3053
    引言它还是来了。这题我尝试写过一次,寄了。然后开摆了。现在决定重新补一补这题。敬请收看:myee调长剖调到CSP还没有调出来的惨状!欢迎来看我什么时候补掉。当然也可......
  • loj3885. 「eJOI2022」Bounded Spanning Tree
    草稿:非树边\(u,v,[l,r]\)把\(u,v\)路径上所有边上界与\(r-1\)取个\(\min\)。剩下的边左端点排序后贪心,每次取右端点最小的一个元素。开始只考虑树边。当前加入一......
  • 10.7校赛初赛
    整体难度不大,但是因为前期冲的太猛了,15分钟做了3道题,后期跟风做题,看着别人都6题甚至AK了,就有点慌张,后期基本上没有深入思考,状态很浮躁,导致最终结果很差。因为后一个小时都......
  • LOJ #2351. 「JOI 2018 Final」毒蛇越狱
    题面传送门奇妙的看上去不能过的题目。首先有一个非常sb的暴力,大概就是枚举?的子集,然后统计,时间复杂度\(O(2^{cnt_1})\)单次。直接算没有优化空间,考虑子集容斥,先FWT预处......