D. Paths on the Tree

这篇具有很好参考价值的文章主要介绍了D. Paths on the Tree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem - 1746D - Codeforces

D. Paths on the Tree,codeforces,算法

思路:先分析一下题意,根据第一条性质,每次只能够从1开始,而第二条性质则表明对于每个节点来说,经过这个节点的子节点的路径条数应该尽量均衡,最大值与最小值相差不能超过1,所以我们考虑,如果当前要选择k个路径,而当前节点有cnt个子节点,那么每个子节点应该至少经过k/cnt个,同时有k%cnt个需要经过k/cnt+1个,那么我们发现这个问题可以递归的解决,那么我们可以考虑用树形dp,我们将f[i][0]表示以i为根,并且经过ki个,f[i][1]表示以i为根并且经过ki+1个,那么对于叶子节点来说,f[i][0]=cost[i]*k,f[i][1]=cost[i]*(k+1),而对于非叶子节点来说,因为所有的子节点都至少经过ki个,所有我们先将所有子节点的f[j][0]求和为sum,令f[i][0]=f[i][1]=sum,那么我们还要再经过k%cnt个,那么我们就是挑几个子节点,然后让他变为f[j][1],那么我们可以将所有f[j][1]-f[j][0]排个序,按照降序排序,那么我们只需要将差值加上,就相当于这个变为了f[j][1],所以我们只需要求一下前k%cnt的和即可,这是对于f[i][0]来说,而对于f[i][1]来说,则还要多出来一次,那么我们只需要求和倒k%cnt+1即可,并且k%cnt+1按照相同的方法取最大的k%cnt+1个一定也是正确的,因为k%cnt最大为cnt-1个,加一为cnt个,正好等于子节点的个数,所以一定是合法的取法文章来源地址https://www.toymoban.com/news/detail-705323.html

// Problem: D. Paths on the Tree
// Contest: Codeforces - Codeforces Global Round 23
// URL: https://codeforces.com/problemset/problem/1746/D
// Memory Limit: 256 MB
// Time Limit: 3000 m

#include<bits/stdc++.h>
#include<sstream>
#include<cassert>
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}

int T,hackT;
int n,m,k;
int h[N],e[M],ne[M],idx;
ll f[N][2];
int cost[N];

void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int k) {
	f[u][0]=(ll)cost[u]*k;
	f[u][1]=(ll)cost[u]*(k+1);
	int cnt=0;
	for(int i=h[u];i!=-1;i=ne[i]) {
		int j=e[i];
		cnt++;
	}
	if(!cnt) return ;
	int a=k/cnt,b=k%cnt;
	
	vector<ll> vis;
	for(int i=h[u];i!=-1;i=ne[i]) {
		int j=e[i];
		dfs(j,a);
		f[u][0]+=f[j][0];
		f[u][1]+=f[j][0];
		vis.push_back(f[j][1]-f[j][0]);
	}
	
	sort(vis.begin(),vis.end(),[&](ll &a,ll &b){
		return a>b;
	});
	
	for(int i=0;i<b;i++) f[u][0]+=vis[i];
	for(int i=0;i<=b;i++) f[u][1]+=vis[i];
}

void solve() {
	n=read(),k=read();
	
	memset(h,-1,sizeof(int)*(n+4));
	idx=0;
	
	for(int i=2;i<=n;i++) {
		int c=read();
		add(c,i);
	}
	
	for(int i=1;i<=n;i++) cost[i]=read();
	
	dfs(1,k);
	
	printf("%lld\n",f[1][0]);
}   

int main() {
    // init();
    // stin();
	// ios::sync_with_stdio(false); 

    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}          

到了这里,关于D. Paths on the Tree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • D. Li Hua and Tree(set操作)

    Problem - D - Codeforces   李华有一个有n个顶点和n -1条边的树。树的根是顶点1。每个顶点i的重要性为a。将子树的大小表示为该子树中顶点的数量,将重要性表示为该子树中顶点的重要性之和。将非叶顶点的重子结点表示为具有最大子树大小的子结点。如果存在多个重子,则重子

    2023年04月13日
    浏览(45)
  • Codeforces Round 890 (Div. 2) D. More Wrong(交互题 贪心/启发式 补写法)

    题目 t(t=100)组样例,长为n(n=2000)的序列 交互题,每次你可以询问一个区间[l,r]的逆序对数,代价是 要在的代价内问出最大元素的位置,输出其位置 思路来源 neal Codeforces Round 890 (Div. 2) supported by Constructor Institute D (交互+分治) 附加强 - 知乎 题解 赛中开题顺序大失败没看这个

    2024年02月14日
    浏览(39)
  • CF1120 D. Power Tree 巧妙的图论转化

    传送门 [前题提要]:无 题目描述: 考虑对一个点的子树的所有 叶子节点 进行增减任意值.不难联想到对一个点的子树的 所有节点 增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改. 考虑记录一个点的所有叶子节点,并且按照 d f s dfs df s 序将其

    2024年02月10日
    浏览(40)
  • SVN出现Cleanup failed to process the following paths...

    SVN报错,需要执行SVN的清理命令clean up,但clean up时出现错误Cleanup failed to process the following paths... 解决办法: 1、clean up的窗口,勾选Break locks和Fix time stamps(简单方便); 2、通过sqlite3.exe,下载地址https://www.sqlite.org/download.html,放在.svn目录下执行; 3、通过SQLite文件可视化工

    2024年02月07日
    浏览(53)
  • CodeForce[1500-2000]——1946C Tree Cutting

    Ccodeforce刷题日记 题目大意: 给你一个n个节点的树,将树的k条边移除,剩下的最小的联通块的节点数量为x,现在要求出x的最大值。 思路: 求最小值的最大,很容易想到二分法,二分最小联通块的节点数x,利用dfs将树分块,当块数量达到x时就分下一组,如果最后一组没达

    2024年04月22日
    浏览(27)
  • K Shortest Paths算法之Eppstein algorithm

    Eppstein的算法是David Eppstein于1998年提出的一种高效且易于实现的k条最短路径寻找方法。它的时间复杂度为O(m + n log n + k),其中m是边的数量,n是节点的数量,k是要寻找的路径数。相较于其他方法,它具有较好的性能和实用性。 1.对于给定的图G(V, E),构造所有节点到目标节点

    2024年02月09日
    浏览(29)
  • Codeforces Round 911 (Div. 2) C. Anji‘s Binary Tree (DFS + 树)

    题目 思路:         dfs树的每一条到叶子的路径, 并计算路径中需要修改的个数, 在这些个数中取最小值 注意:         本题中的树是以每个结点的左右孩子是什么的形式给出的, 所以可以不用建树, 只需保存每个结点的左右孩子是什么即可。 代码:

    2024年01月16日
    浏览(43)
  • 【LeetCode 算法】Unique Paths III 不同路径 III 暴力DFS

    在二维网格 grid 上,有 4 种类型的方格: 1 表示起始方格。且只有一个起始方格。 2 表示结束方格,且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目

    2024年02月14日
    浏览(51)
  • Codeforces Mahmoud the Thief(思维)

    As Ayoub was going home from Mahmoud\\\'s house, he remembered that he forgot his hard disk, which contains the solutions to n problems from the JU Flash contest. The ith problem has size ai. While panicking, he remembered that he installed a software that prevented the user from copying any files and only allowed the files to be cut from the hard disk in

    2024年02月09日
    浏览(42)
  • 树上启发式合并(dsu on tree)

    dsu on tree dsu text{dsu} dsu 一般指 disjoint set union text{disjoint set union} disjoint set union ,即并查集。 dsu on tree text{dsu on tree} dsu on tree 指树上合并与查询操作,但它的实现和普通的并查集并无关联,两者的共同点仅仅在于都能合并集合和查询而已。 dsu on tree text{dsu on tree} d

    2024年02月16日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包