16浙理工新生赛 K KI的目标 (树上dfs)

迷南。 2022-07-14 11:11 114阅读 0赞

题目链接：[点击打开链接][Link 1]

##  ##

##  ##

题解：不断维护：ans += dfs(u,v,max( val\[v\], cur-w) )

AC代码：

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N=1000000+10;
    struct Edge{
    	int v,w,next;
    	Edge(){}
    	Edge(int _v,int _w,int _next):v(_v),w(_w),next(_next){}
    	
    }e[N*2];
    
    int head[N];
    int val[N];
    int n,E;
    int dfs(int o,int u,ll cur)
    {
    	int ans=1;
    	int v,w;
    	for(int i=head[u];~i;i=e[i].next)
    	{
    		v=e[i].v;
    		w=e[i].w;
    		if(v==o)continue;
    	//	printf ("val[%d]=%d, cur-w=%lld\n", v,val[v], cur-w);
    		if(val[v]<cur-w) continue;
    		
    		ans+=dfs(u,v,max( (ll)val[v], cur-w) );
    		
    	}
    	//printf ("u=%d, ans=%d\n", u, ans);
    	return ans;
    }
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		memset(head,-1,sizeof(head));
    		E=0;
    		int u,v,w;
    		for(int i=1;i<n;i++)
    		{
    			scanf("%d%d%d",&u,&v,&w);//u->v
    			e[E]=Edge(v,w,head[u]);
    			head[u]=E++;
    			e[E]=Edge(u,w,head[v]);
    			head[v]=E++;
    		}
    		for(int i=1;i<=n;i++)scanf("%d",&val[i]); //点权 
    		printf("%d\n",dfs(1,1,val[1]));
    	}
    	return 0;
    }

[Link 1]: http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4248

发表评论取消回复

表情：

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

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

相关阅读

相关 16哈理工新生赛 J Another Tree （树上BFS）

题目链接：[点击打开链接][Link 1] <table> <tbody> <tr> <td><span style="font-size:18px">An

淡淡的烟草味﹌/ 2022年07月14日 11:39/ 0 赞/ 65 阅读

相关 16浙理工新生赛 K KI的目标 (树上dfs)

题目链接：[点击打开链接][Link 1] 题解：不断维护：ans += dfs(u,v,max( val\[v\], cur-w) ) AC代码

迷南。/ 2022年07月14日 11:11/ 0 赞/ 115 阅读

相关 16哈理工新生赛 D 陈月亮的数学题（数论）

题目链接：[点击打开题目链接][Link 1] 陈月亮的数学题 Time Limit: 2000 MS Memory Limit: 32768 K Total S

Myth丶恋晨/ 2022年07月14日 11:07/ 0 赞/ 158 阅读

相关 16哈理工新生赛 H 下雪啦（哈希表）

题目链接：[点击打开链接][Link 1] <table> <tbody> <tr> <td><span style="font-size:18px">下雪

╰半橙微兮°/ 2022年07月14日 10:27/ 0 赞/ 143 阅读

相关 16哈理工新生赛 K 小明和字符串（水题）

题目链接：[点击打开链接][Link 1] <table> <tbody> <tr> <td><span style="font-size:18px">小明

野性酷女/ 2022年07月14日 10:21/ 0 赞/ 67 阅读

相关 16哈理工新生赛 I 行编辑器（模拟）

题目链接：[点击打开链接][Link 1] <table> <tbody> <tr> <td><span style="font-size:18px">行编

快来打我*/ 2022年07月14日 10:21/ 0 赞/ 134 阅读

相关 16哈理工新生赛 E Nine Digits （BFS+康拓展开）

<table> <tbody> <tr> <td><span style="font-size:18px">题目链接：<a href="http://acm.

妖狐艹你老母/ 2022年07月14日 09:42/ 0 赞/ 140 阅读

相关 16哈理工新生赛 C 方方正正（证明题）

<table> <tbody> <tr> <td><span style="font-size:18px">方方正正</span></td> </tr>

逃离我推掉我的手/ 2022年07月14日 09:39/ 0 赞/ 59 阅读

相关 16哈理工新生赛 B 修建传送门（双指针）

<table> <tbody> <tr> <td><span style="font-size:18px">题目链接：<a href="http://acm.

心已赠人/ 2022年07月14日 09:29/ 0 赞/ 39 阅读

相关 16哈理工新生赛 A 棋盘村 (dp)

题目链接：[点击打开链接][Link 1] <table> <tbody> <tr> <td><span style="font-size:18px"

超、凢脫俗/ 2022年07月14日 08:46/ 0 赞/ 128 阅读