首页 > 其他分享 >YACS 2023年1月月赛 甲组 T1 树的独立集 题解

YACS 2023年1月月赛 甲组 T1 树的独立集 题解

时间:2023-02-12 00:00:34浏览次数:65  
标签:YACS 挨边 200005 int 题解 甲组 mod

题目链接

半夜 12:00 我不睡觉来这里更文章来了。。。

这次的甲组好简单,第一次 $AK$ 了,

这题看上去很难,要求什么不挨边,其实分析一下就是 树形 $DP$。

首先要求不挨边,所以我们需要每个点选不选的状态,那么设 $f[i][0/1]$

为以 $i$ 为根的子树,$i$ 选或者不选的方案数。

如果 $i$ 选,那么儿子就不能选,否则儿子选不选无所谓。

乘起来就好了,我用的 $dfsdp$,在算好儿子后直接加父亲,节约了点码量。

代码:

#include <vector>
#include <iostream>
#define int long long
using namespace std;
int n, mod = 1000000007;
int p[200005], f[200005][2];
vector <int> v[200005];
int dfs (int x) {
    f[x][0] = f[x][1] = 1;
    for (int i = 0;i < v[x].size (); i ++) dfs (v[x][i]);
    -- f[x][0];
    f[p[x] ][0] = f[p[x] ][0] * (f[x][1] + f[x][0] + 1) % mod;
    f[p[x] ][1] = f[p[x] ][1] * (f[x][0] + 1) % mod;
    return (f[x][0] + f[x][1] + 1) % mod;
}
signed main () {
    cin >> n;
    for (int i = 2; i <= n; i ++) {
        cin >> p[i];
        v[p[i] ].push_back (i);
    }
    cout << dfs (1);
    return 0;
}

 

标签:YACS,挨边,200005,int,题解,甲组,mod
From: https://www.cnblogs.com/Xy-top/p/17113103.html

相关文章

  • 题解 LGP9018【[USACO23JAN] Moo Route G】
    problem现在有一条数轴,\(t\)表示当前时刻。在\(t=0\)时Bessie恰好处在\(x=0\)的位置。接下来,每秒钟Bessie会向左或者向右移动一个单位距离,我们保证Bessie是在......
  • flannel 低版本glog flag redefined error 问题解决
    最近在构建一个老版本的flannel的时候碰到了此问题,记录下,方便使用解决方法glideinstall--strip-vendor--strip-vcs参考资料https://stackoverflo......
  • go: cannot find main module, but found glide.lock 问题解决
    解决方法exportGO111MODULE=auto说明此问题主要是老golang项目构建可能会出现的,新的一般不对有此问题(都基于gomod了)参考资料https://github.co......
  • abc289g题解
    考虑枚举卖出的物品个数\(i\),把\(b_i\)从大到小排序。题目的某人会买物品的条件转化为\(b_i\geqp_j-c_j\),这说明卖出的物品的集合是排序后\(b\)的一段前缀,且卖出\(i\)个......
  • CF793G Oleg and chess 题解
    \(\text{类似于主席树优化建图,直接放一张图片。}\)#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<vector>#include<map>#include......
  • 【题解】CF997C Sky Full of Stars
    简记一下高维二项式反演的套路。思路高维二项式反演。首先意识到\(n\leq10^6\)且计数,并且求“至少”,所以考虑用二项式反演处理。这里如果用一维的二项式反演,可能......
  • 【题解】P4464 [国家集训队] JZPKIL
    仙气飘飘莫反题。显现出了很多推式子习惯的问题。思路莫反+伯努利数+Pr。首先根据\(\operatorname{lcm}(x,y)=\frac{xy}{\gcd(x,y)}\)可以化简:\(\sum\limits......
  • P9033题解
    P9033「KDOI-04」XORSum题解题目链接传送门题意简述构造一个长度为\(n\),值域为\([0,m]\)的异或和为\(k\)的序列,如果不存在则输出\(-1\)。题目分析首先很容易......
  • CF1268B题解
    CF1268B题解题目翻译给你一个杨表,用一个有\(n\)个元素的数组\(a\)表示杨表每一列的高度。你需要用\(1\times2\)或\(2\times1\)的骨牌填充这个杨表,求出最多......
  • 题解:[PA2021] Drzewo czerwono-czarne
    题目链接:[PA2021]Drzewoczerwono-czarne首先对于起始和终止相同以及起始中只有一种颜色并且终止和起始不相同这两种情况是平凡的。考虑最后一步,一定是将某一条边上的一......