hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共6篇）

Work Group 来自专栏

题意：有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？思路：树状dpdp[v][0/1]表示第v个节点在满足条件时该子...

树状dp

2021-02-22

1 698

Tree with Small Distances 来自专栏

题意：给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？思路：你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。代码： #include<bits/s...

最小支配集树状dp

2020-11-19

3 840

Accumulation Degree

题意：给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。思路：树状dp+换根：flow[i]为以i为子树i到子树叶子节点的流量最大值。ans[i]表示以i为根节点时的答案。flow[u]= min(flow[v],cost(u,v))(v为u的子节...

换根树状dp

2020-08-22

1 775

选课

题意：你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？思路：树状dp没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条...

树状dp

2020-08-22

5 537

蓝魔法师

题意：给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。思路：树形dp：从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。sum...

树状dp

2020-08-12

2 817

旅游

题意：有一个n个城市有（n-1）条道路的无向图，有二人打算旅游，第一天住在s市，并浏览了周围距离不大于1的城市，每天会选择一个城市住，他们不想住在已经浏览过的城市，并且他们想旅游时间尽可能长.求最长旅游多少天？思路：树状dp,dp[v][0/1]表示以v为根节点的树，根节点分是否住的的最大旅游天数...

树状dp

2020-06-04

1 689