P3478 [POI2008] STA-Station

题面

给定一个 \(n\) 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

分析

本题可以用树形DP做。

首先,把树按照链式前向星的方法保存。

然后考虑第 \(i\) 个点的深度来DP,先求 \(DP_1\),然后往下推,深度减小了 \(size_v\),增加了 \(n-size_v\)。所以用 \(O(n)\) 的算法来DP,然后直接用 \(O(n)\) 统计最大值。

贴上代码

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

const int N = 1e6+10;
struct Edge{
	int next,to;
} e[N<<1];

int deep[N],head[N],length;
int siz[N];
long long dp[N];
int n,a,b;
int result=0;

void add(int u,int v){
	e[++length].to=v;
	e[length].next=head[u];
	head[u]=length;
}

void dymanic_planning(int u,int fa){
	siz[u]=1;
	dp[u]=deep[u];
	for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        deep[v]=deep[u]+1;
        dymanic_planning(v,u);
        siz[u]+=siz[v];
        dp[u]+=dp[v];
    }
}

void solve(int u,int fa){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dp[v]=dp[u]-siz[v]+n-siz[v];
        solve(v,u);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dymanic_planning(1,0);
	solve(1,0);
	for(int i=1;i<=n;i++){
		if(dp[result]<dp[i]){
			result=i;
		}
	}cout<<result<<endl;
	return 0;
}

推荐这些文章:

动态规划DP入门问题----最大连续子序列,最长不下降子序列(可以不连续),最长公共子序列

一、最大连续子序列
1.题目叙述

对于一个数字序列A1A2A3...An,求出连续子序列的最大和,如对于序列-2,11,-4,13,-5,-2,其中的最大序列和是11+(-4)+13=20 

2.动态规划解法
将问题拆分成子问题,即dp[i]表示以A[i]为结尾的子序列的最大和,最后对于这些dp数组找出最大值即可,状态转移方程为:

dp[i] = max{ dp[i-1] + A[i] }  状态dp[i]表示,当前以A【i】结尾的子序列的最大和

3.方法一是经典算法,方法二是根据状态方程优化而来。

#include<iostream>
#inclu...

动态规划-最长连续递增序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
思路:
严格和前一个数比较,而不是前面的某个数。
代码:

class Solution {
public int findLengthOfLCIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
if (nums[i] > nu...

leetcode(c++)(区间DP)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestPalindrome(string s)
{
int n = s.size();
vector<vector<bool>>dp(n,vector<bool>(n));
int start = 0, end = 0;
for(int i = n - 1; i >= 0; --i)
{
...

#排列组合,dp#LOJ 6069 「2017 山东一轮集训 Day4」塔

题目传送门

分析
两点之间的最小距离其实是由两点高度最大值决定的,
求出长度为 \(n\) 的排列所需距离的方案数,剩下还能放的距离可以用插板法放进去。
也就是 \(\sum_{i=1}^{n^2}f_i*\binom{m-i+n}{n}\)
设 \(dp[i][j][k]\) 表示 \(1\sim i\) 被分成 \(j\) 段所需距离为 \(k\) 的方案数。
新开一段就是 \(dp[i][j+1][k+1]+=dp[i-1][j][k]*(j+1)\)(有 \(j+1\) 个位置可以选)
合并到一段开头或结尾就是 \(dp[i][j][k+i]+=dp[i-1][j][k]*(2*j...

#10159. 「一本通 5.2 练习 2」旅游规划

原题传送门
题意
由于有 \(n\) 个交通路口, \(n - 1\) 条街道, 所以我们可以断定, 这是一颗树.
又由于让我们求出这棵树的最长路径, 很简单就能想到树形dp (貌似两遍 dfs 更简单?)
简化一下: 给定一棵树, 求出他的 所有 直径. (注意"所有", 这是题目的难点.)
直径
要想做这题, 首先要会求树的直径, 这里默认已经学会.
路径
首先需要用 dfs1 求出直径的长度 length.
显然, 当点 \(u\) 满足 \(dp[u][0] + dp[u][1] = length\) 时他为某一条直径上的点.这个很好找, 只需要声明一个 dfs2 遍历即可.
再从...

P1048 [NOIP2005 普及组] 采药 题解

P1048 [NOIP2005 普及组] 采药解法一

#include<iostream>
#include<cstring>
using namespace std;
const int Maxn=110;
const int Maxv=1010;
int V,n,ans=0;
int w[Maxn],c[Maxn];
int dp[Maxn][Maxv];
void dfs(int i,int v)
{
if (dp[i][v]!=-1) return ;
if (i==0)
{
dp[i][v]=0;
}
else
{
dfs(i-1,v...

cf685 B. Kay and Snowflake(树形dp,树的重心)

题意:
找每棵子树的重心。(叙述与原题意有点不同,但可以按这个做)
思路:
首先dfs,求每棵子树的大小 sz[u] ,以及最大的直接儿子子树的大小 mx[u]
以 u-子树 中的某点 cen 为重心,最大的连通块大小为 get = max(sz[u]-sz[cen], mx[cen])
当重心沿着树链往上走(不超过u)时,get要么单调递增,要么先递减后递增。那么每个让 v-子树的重心往上走,尝试更新答案。
注意每个重心往上走的过程是单调的,不需要往回走。这保证了复杂度是 \(O(n)\)
const int N = 3e5 + 5;
int n, q, fa[N];

int h[N],...

动态规划:树的最长路径 树形DP

树的最长路径

题目描述  给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。
  现在请你找到树中的一条最长路径。
  换句话说,要找到一条路径,使得使得路径两端的点的距离最远。
  注意:路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n−1 行,每行包含三个整数 a b c
输出格式
输出一个整数,表示树的最长路径的长度。
数据范围
1 ≤ n ≤ 100001 ≤ a i , b i ≤ n -1e5<=ci<=1e5
 
思路:
对每一个结点找到向下查找的max d1 和第二大 d2 则最大值就...

YbtOJ-交换游戏【树链剖分,线段树合并】

正题

题目大意
给出两棵树,对于第一棵树的每一条边\((x,y)\)询问有多少条在第二棵树上的边\((u,v)\)与其交换(连接的序号相同)后两棵树依旧是一棵树。
\(1\leq n\leq 2\times 10^5\)

解题思路
先只考虑一棵树的合法情况,对于第二棵树的边\((u,v)\)交换过来合法的当且仅当\((x,y)\)在\(u\rightarrow v\)路径上,同理的对于第二棵树合法当且仅当\((u,v)\)在\(x\rightarrow y\)路径上。
那么考虑限制一个条件,第二个条件用数据结构查询。
我们把所有的\((u,v)\)用树上差分挂在第一棵树的\(u\righ...

【动态规划】【线性DP】 45. 跳跃游戏 II

45. 跳跃游戏 II - 力扣(LeetCode) (leetcode-cn.com)

下述均为对: 宫水三叶的题解的理解。原解释请直接 访问
我们知道最后一个点前面可能会有很多个点能够一步到达最后一个点。

也就是有 f[n−1]=min(f[n−k],...,f[n−3],f[n−2])+1
然后我们再来考虑集合 f[n−k],...,f[n−3],f[n−2] 有何特性。
不然发现其实必然有 f[n−k]<=...<=f[n−3]<=f[n−2]。
这个k 其实就是跳过来的步长,打个比方说, nums[2]=5, 那么从第2个台阶 就可以蹦五步 到达第7个台阶 ...

文章标题:P3478 [POI2008] STA-Station
文章链接:https://www.dianjilingqu.com/51527.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>