CF 1060E. Sergey and Subway

题目链接
题意:给你一棵树,然后连接两个有公共邻居的点,问你连完后,任意两点的距离之和。
一开始看这种题,还不怎么会做,借鉴了这位大佬的博客,get到了新技能,当我们求树上任意俩点的距离之时,可以转化问题,不看点,而看边,每条边的使用次数是固定的,每条边使用的次数为:这条边左边的顶点数*右边的顶点数,而由于我们可以将相隔一个点的两个点连起来,所以,如果是偶数的距离,我们可以2个2个跳,就是距离的一半,奇数呢就是(距离+1)/2,而奇数的距离只能在偶数和奇数层产生,所以用 d p [ n o w ] [ 2 ] dp[now][2] dp[now][2]记录当前节点 n o w now now的层数, d p [ n o w ] [ 1 ] dp[now][1] dp[now][1]表示由上一个节点pre出发,要经过 n o w now now才能到的点数(包括自己),那么 ( n d p [ n o w ] [ 1 ] ) d p [ n o w ] [ 1 ] (n-dp[now][1])*dp[now][1] (ndp[now][1])dp[now][1]就表示 p r e > n o w pre->now pre>now这条边的使用次数。

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
vector<int>v[N];
int n, dp[N][3];
void dfs(int now, int pre, int sta) {
	dp[now][1]++;
	dp[now][2] = sta;
	for (int k : v[now]) {
		if (k == pre)continue;
		dfs(k, now, sta ^ 1);
		dp[now][1] += dp[k][1];
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int s, t;
		cin >> s >> t;
		v[s].pb(t);
		v[t].pb(s);
	}
	dfs(1, 0, 0);
	LL ans, res;
	ans = res = 0;
	for (int i = 1; i <= n; i++) {
		ans += 1ll*dp[i][1] * (n - dp[i][1]);
		res += dp[i][2];
	}
	ans += 1ll*res * (n - res);
	cout << ans / 2;
	return 0;
}
全部评论

相关推荐

来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务