思路:

树形dp,首先使用dp计算以1为根的时候的最大分数,同时得到各个子树i的最大分数dp[i]。然后利用前面得到的dp数组分别计算以其他每个点作为根的时候的最大分数。

实现:

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
vector<int> G[N];
ll cnt[N], dp[N];
int n;
void dfs(int u, int p)
{
cnt[u] = ;
for (int i = ; i < G[u].size(); i++)
{
int t = G[u][i];
if (t == p) continue;
dfs(t, u);
cnt[u] += cnt[t];
dp[u] += dp[t];
}
dp[u] += cnt[u];
}
void dfs2(int u, int p, ll x, ll& ans)
{
ans = max(ans, dp[u] - cnt[u] + x + n);
for (int i = ; i < G[u].size(); i++)
{
int t = G[u][i];
if (t == p) continue;
dfs2(t, u, dp[u] - cnt[u] - dp[t] + x + n - cnt[t], ans);
}
}
int main()
{
int a, b;
while (cin >> n)
{
for (int i = ; i <= n; i++) G[i].clear();
memset(cnt, , sizeof cnt); memset(dp, , sizeof dp);
for (int i = ; i <= n - ; i++)
{
cin >> a >> b;
G[a].push_back(b); G[b].push_back(a);
}
dfs(, );
ll maxn = dp[];
for (int i = ; i < G[].size(); i++)
{
int t = G[][i];
dfs2(t, , dp[] - dp[t] - cnt[t], maxn);
}
cout << maxn << endl;
}
return ;
}

最新文章

  1. jquery1.7.2的源码分析(四)$.Deferred(2)
  2. Hadoop安装及配置
  3. 开源的运维机器人hubot原理
  4. Delphi中window消息截获的实现方式(2)
  5. 在ASP.NET中实现OAuth2.0(二)之打造自己的API安全策略
  6. scjp考试准备 - 4 - 关于数组
  7. 540B :School Marks
  8. 进程间通信之FIFO
  9. java新手笔记33 多线程、客户端、服务器
  10. win10中的vmware桥接模式异常,不能设置同网段ip
  11. CTF入门指南
  12. Vue学习之路---No.4(分享心得,欢迎批评指正)
  13. 简单总结几种常见web攻击手段及其防御方式
  14. 8 ServletContext
  15. 在 Activity 中实现 getContentView 操作
  16. [译]在vuejs中使用任意js库
  17. arduino使用oled显示时间MQ_2温湿度
  18. Android Native Hook技术(一)
  19. Android 之窗口小部件高级篇--App Widget 之 RemoteViews
  20. 破解VS

热门文章

  1. IAR添加debug和release选项
  2. [2019年湘潭大学程序设计竞赛(重现赛)H chat][背包dp]
  3. SQL Server遇到的错误和有用的tools
  4. 配置apt源
  5. [Luogu] 矩阵加速(数列)
  6. [USACO15DEC] 最大流Max Flow &amp;&amp; Tarjan 线性 LCA 教学?
  7. Spoj Query on a tree SPOJ - QTREE(树链剖分+线段树)
  8. 文件描述符、文件表项、V节点表项的一些总结
  9. prometheus简单监控Linux,mysql,nginx
  10. kubernetes案例 tomcat+mysql