很妙的一个树形DP问题,简单考虑了一下就过了

https://ac.nowcoder.com/acm/contest/2927/E

主要就是推公式(公式有点长呀)

大概就是这样,其实挺简单的。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const ll mod = 998244353;
int head[maxn];
int cnt = 1;
ll sum[maxn];
ll son[maxn];
ll dp[maxn]; struct Node {
int p;
int next;
}G[2*maxn];
int n;
void add(int be, int en) {
G[cnt].p = en; G[cnt].next = head[be]; head[be] = cnt;
cnt++;
}
int dfs(int x,int fa) {
son[x] = 1;
for (int i = head[x]; i; i = G[i].next) {
int p = G[i].p;
if (p == fa) continue;
dfs(p, x);
son[x] += son[p];
sum[x] = ( sum[x] + son[p] + sum[p]) % mod;
dp[x] = (dp[x] + dp[p] + 2 * sum[p] + son[p]) % mod;
}
return 0;
} int dfs2(int x, int fa) {
for (int i = head[x]; i; i = G[i].next) {
int p = G[i].p;
if (p == fa) continue; ll ans = ((dp[x] - (dp[p] + 2 * sum[p] + son[p])) % mod + mod) % mod;//dp
//sum
ll cns = ((sum[x] - (sum[p] + son[p])) % mod + mod) % mod; dp[p] = ((dp[p] + ans + 2 * cns + n - son[p]) % mod + mod) % mod;
sum[p] = ((sum[p] + cns + n - son[p]) % mod + mod) % mod; dfs2(p, x);
}
return 0;
}
int main() {
int be, en; scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d %d", &be, &en);
add(be, en);
add(en, be);
}
dfs(1, -1);
dfs2(1, -1);
ll a = 0; for (int i = 1; i <= n; i++) {
a = (a + dp[i]) % mod;
}
printf("%lld\n", a);
return 0;
}

  

最新文章

  1. 序列化多个form表单内容同时提交
  2. Sublime Text3 配置 NodeJs 环境
  3. centos7查看端口命令
  4. XdbxAnalysis
  5. EVE ToDo
  6. 使用JQuery能做什么(zz)
  7. 串口通信类,WPF
  8. [swustoj 243] 又是一年CET46
  9. python学习第六天
  10. Oracle函数+for循环
  11. lintcode:递归打印数字
  12. HW4.29
  13. 【HDOJ】2386 Dart Challenge
  14. hdu 4404 Worms(多边形与圆的交)
  15. 20162311 实验三 敏捷开发与XP实践 实验报告
  16. IPv6原理、应用与实践
  17. 网络小白之WAN与LAN的区别
  18. python io-os
  19. html5中如何更改、去掉input type默认样式
  20. Pycharm中自动生成作者,日期等信息

热门文章

  1. python 数据的读取
  2. ROW_NUMBER(),不允许并列名次、相同值名次不重复,结果如123456……
  3. HUD-1708_FatMouse and Cheese
  4. Quick BI 3.0 - 强大的多维分析表格:交叉表
  5. 规模化落地云原生,阿里云即将重磅亮相 KubeCon China
  6. oracle函数 ceil(x)
  7. 用laravel搭一个微信公众号后台
  8. angular select框 option空行
  9. http端口
  10. java线程与进程的比较