当前位置：首页 > article >正文

E. Sergey and Subway(思维 + dp)

article 2024/11/15 14:20:43

Problem - E - Codeforces

Sergey Semyonovich 是 N 市县的市长，他一直在思考如何进一步改善 Nkers 的生活。不幸的是，几乎所有可以做的事情都已经完成了，白天他已经没有更多的想法（他现在喜欢在晚上睡觉）。然而，他的助手们已经找到了一个解决方案，他们在纸张上绘制了一座虚构的城市，并建议市长可以提出其改进意见。

现在，他手头有一张包含 n 个地铁站的虚构城市地图。有些站点之间通过隧道直接相连，使整张地图成为一棵树（助手们时间和热情均不足）。这意味着每对站点之间存在仅有一条简单路径。如果一条路径只使用每条隧道不超过一次，则称其为简单路径。

Sergey Semyonovich 最喜欢的质量目标之一是所有站点之间的两两距离之和。两个站点之间的距离是它们之间路径上可能的隧道数量的最小值。

Sergey Semyonovich 决定在地铁图上添加新的隧道。特别地，他连接了原来没有直接隧道相连但有共同邻居的任意两个站点 u 和 v，也就是说，存在一个站点 w，使得原来的地图中 u 和 w 之间存在一条隧道，w 和 v 之间存在一条隧道。现在请你计算新地图中所有站点对之间距离的总和。

输入格式第一行包含一个整数 n (2≤n≤200000) — 市长助手们绘制的虚构城市中地铁站点的数量。接下来 n−1 行，每行包含两个整数 ui 和 vi (1≤ui,vi≤n，ui≠vi)，表示这两个索引号的站点通过直接隧道相连。

保证这 n 个站点和 n−1 条隧道形成一棵树。

输出格式输出一个整数，表示 Sergey Semyonovich 在原始地图上为所有具有共同邻居但没有直接连接的站点之间添加新的隧道后，所有站点对之间距离的总和。

Examples

input

Copy

output

Copy

input

Copy

output

Copy

题解:
通过我们划图发现,如果按题目中那样加边,原来两点距离为一的距离还为一,

(按照我的错误想法,距离不为1的,减1的贡献即可,但是不是这样的,我举得例子点数太少,不具有代表性)

实际应该是

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 1e9 + 7;
vector<int> p[200050];
int dp[200050];
int ans = 0;
int cnt = 0;
void dfs(int x,int fa,int deep)
{
	dp[x] = 1;
	if(deep&1)
	cnt ++;
	for(auto ne:p[x])
	{
		if(fa == ne)
		{
			continue;
		}
		dfs(ne,x,deep + 1);
		dp[x] = dp[ne] + dp[x];
		
	}
}
void solve()
{
	int n;
	cin >> n;
	for(int i = 1;i < n;i++)
	{
		int x,y;
		cin >> x >> y;
		p[x].push_back(y);
		p[y].push_back(x);
	}
	dfs(1,0,0);
	for(int i = 2;i <= n;i++)
	{
		ans += dp[i]*(n - dp[i]);
	}
	ans = ans - (ans - cnt*(n - cnt))/2;
	cout << ans;
}

signed main()
{
//	ios::sync_with_stdio(0 );
//	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve(); 
	}
}

1~5的距离不加额外边应该是4,加了只后变成了2,

2~5的距离不加额外边是3,加了后变成2

其实就是所有的距离变成(c + 1)/2

首先原图的距离很好求,可以通过求每个点子节点的个数*(n - 子节点的个数相加求到,代表每条边对距离的贡献

那如何减去加边后的贡献呢,我们可以把点数分为,深度在奇偶层,只有奇偶层间的距离永远是1 + 一个偶数(可能是0),由于1是不会改变的,我们相当于把所有无法删去的1给减去了,剩下距离整除2即可

我们的到奇偶层对数为cnt*(n - cnt)

答案就为ans - (ans - cnt*(n - cnt))/2

查看全文

http://www.kler.cn/a/17890.html