G.树上求和

偏执的太偏执、 2023-07-18 09:15 61阅读 0赞

[G.树上求和][G.]

题意：  
给你一棵n个顶点n-1条边的树，让你给n-1条边分别赋值1~n-1 ，每个数只能用一次，求整棵树最终任意两点之间的权值和。

题解：  
我们只需要计算每条边被访问了多少次就行了，然后根据访问次数从小到大排序，最小的赋值最大的、…、最大的赋值最小的。

访问次数=该条边左边的端点数 \* 该条边右边的端点数（ size \* (n-size) ）

dfs找出每个顶点左边或者右边的个数，计算访问的次数，从小到大计算就ok了。

code：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    ll he[maxn],ver[maxn],ne[maxn],vis[maxn];
    ll size[maxn],ans[maxn];
    ll cnt=0;
    void add(ll x,ll y)
    { 
    	ver[++cnt]=y;
    	ne[cnt]=he[x];
    	he[x]=cnt;	
    } 
    void dfs(ll u)
    { 
    	size[u]=1;
    	for(int i=he[u];i;i=ne[i])
    	{ 
    		ll num=ver[i];
    		if(!vis[num])
    		{ 
    			vis[num]=1;
    			dfs(num);
    			size[u]+=size[num];
    		}
    	} 
    }
    int main()
    { 
    	io();
    	ll n;
    	cin>>n;
    	for(int i=1;i<n;i++)
    	{ 
    		ll x,y;
    		cin>>x>>y;
    		add(x,y);
    		add(y,x);
    	}
    	vis[1]=1;
    	dfs(1);
    	for(int i=2;i<=n;i++)
    		ans[i]=size[i]*(n-size[i]);
    	sort(ans+2,ans+n+1);
    	ll sum=0;
    	for(int i=2;i<=n;i++)	
    		sum+=ans[i]*(n-i+1);
    	cout<<sum<<endl;
    	return 0;
    }

[G.]: https://ac.nowcoder.com/acm/contest/4784/G

发表评论取消回复

表情：

评论列表（有 0 条评论，61人围观）

还没有评论，来说两句吧...

相关阅读

相关【树上乘法原理】ICPC Shanghai 2021 G, Edge Groups

[http://oj.daimayuan.top/course/8/problem/400][http_oj.daimayuan.top_course_8_problem_40

àì夳堔傛蜴生んèń/ 2024年03月22日 21:50/ 0 赞/ 102 阅读

相关【树上操作】定长裁剪 CF1833 G

[Problem - G - Codeforces][] 题意：给定一棵n个节点的树，请你减掉一些边，使得剪掉后的每个树只有三个节点，如果可以，第一行返回减掉边的数

今天药忘吃喽~/ 2024年03月18日 00:38/ 0 赞/ 105 阅读

相关【dfs序+线段树】求和

今天终于把昨天的任务给写了呃呃 [C-求和\_2021秋季算法入门班第十三章习题：LCA (nowcoder.com)][C-_2021_LCA _nowcoder.co

「爱情、让人受尽委屈。」/ 2024年03月17日 10:23/ 0 赞/ 85 阅读

相关【树上染色】CF1760G

[Problem - G - Codeforces][] 题意： ![19660cc196e8479e96351e9dab4e653f.png][] 思路：我们需要找

柔光的暖阳◎/ 2024年03月16日 11:57/ 0 赞/ 61 阅读

相关（枚举 + 树上倍增）Codeforces Round 900 (Div. 3) G

[Problem - G - Codeforces][] 题意： ![34732364ff234c308c2bde9cde9b9b34.png][] 思路：首先，目标

亦凉/ 2024年02月26日 07:04/ 0 赞/ 63 阅读

相关线段树的修改和求和

网上有很多讲线段树原理的文章，如果你是第一次接触【线段树】这种数据结构，看这些文章估计会把你脑子弄得很晕。强烈推荐直接看这个视频：[线段树][Link 1]； 1.线段树有

柔情只为你懂/ 2023年09月29日 09:06/ 0 赞/ 3 阅读

相关 G.树上求和

[G.树上求和][G.] 题意：给你一棵n个顶点n-1条边的树，让你给n-1条边分别赋值1~n-1 ，每个数只能用一次，求整棵树最终任意两点之间的权值和。题解：

偏执的太偏执、/ 2023年07月18日 09:15/ 0 赞/ 62 阅读

相关 lintcode206. 区间求和 I 线段树

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 \[start, end\] 。对于每个查询，计算出数组中从

柔光的暖阳◎/ 2023年07月06日 13:29/ 0 赞/ 58 阅读

相关 x 树上求和

树上求和 https://ac.nowcoder.com/acm/problem/19428 include<bits/stdc++.h>

川长思鸟来/ 2022年09月04日 10:58/ 0 赞/ 154 阅读

相关线段树+区间求和

P3372 【模板】线段树 1 如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上x 2.求出某区间每一个数的和输入输出格式输入格式：

偏执的太偏执、/ 2021年12月09日 15:49/ 0 赞/ 422 阅读