【Luogu3478】【POI2008】STA-Station(动态规划)
规划 动态
2023-09-11 14:14:41 时间
【Luogu3478】【POI2008】STA-Station(动态规划)
题面
题目描述
给出一个\(N(2<=N<=10^6)\)个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
题解
考虑直接对于每个点计算一次
时间复杂度\(O(n^2)\)显然无法接受
所以,考虑只进行一次\(DFS\)在通过递推求解
如果已经知道根节点的答案的话
那么,他的儿子节点很容易的可以递推出来:
\(Ans{[son]}=Ans[father]+n-2*size[son]\)
所以可以\(O(n)\)求解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 1200000
#define ll long long
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next;
}e[MAX<<1];
int h[MAX],cnt=1;
int n;
ll dep[MAX],sum[MAX],size[MAX];
ll ans[MAX];
inline void Add(int u,int v)
{
e[cnt]=(Line){v,h[u]};
h[u]=cnt++;
}
void dfs(int u,int ff)
{
sum[u]=dep[u]=dep[ff]+1;size[u]=1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==ff)continue;
dfs(v,u);
size[u]+=size[v];
sum[u]+=sum[v];
}
}
void DFS(int u,int ff)
{
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==ff)continue;
ans[v]=ans[u]+n-2*size[v];
DFS(v,u);
}
}
int main()
{
n=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
dfs(1,0);
ans[1]=sum[1];
DFS(1,0);
int pos=1;
for(int i=1;i<=n;++i)
if(ans[i]>ans[pos])pos=i;
printf("%d\n",pos);
return 0;
}
相关文章
- 新年个人职业目标和规划怎样写?用便签写好个人工作新年规划
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- POJ 1185 炮兵阵地(动态规划+状态压缩)
- 数据结构和算法—动态规划
- LeetCode-808. 分汤【动态规划,概论与统计,记忆化搜索】
- Leetcode学习计划之动态规划入门day14(1314,120)
- Leetcode0393: UTF-8 编码验证(medium, 动态规划)
- 【 【henuacm2016级暑期训练】动态规划专题 K】 Really Big Numbers
- 基于企鹅优化算法的机器人轨迹规划(Matlab代码实现)
- 【路径优化】基于改进的RRT算法的全局路径规划(Matlab代码实现)
- 基于改进粒子群优化算法的UAV三维路径规划研究(Matlab代码实现)
- 高密度城市路线规划的遗传优化算法的matlab仿真,城市点数量达到500个
- 基于蚁群优化算法的三维路径规划算法matlab仿真
- 基于Qlearning强化学习的机器人路线规划仿真
- 64. 最小路径和-动态规划算法
- 剑指 Offer II 011. 0 和 1 个数相同的子数组-动态规划算法
- 解决智力问题-逆向动态规划
- 递归+动态规划求和
- [LeetCode] 516. 最长回文子序列 ☆☆☆(动态规划)
- 动态规划 is beginning。。。。。。。。。
- 动态规划 背包问题算法模板 0-1背包 0-1带价值背包 多重背包问题