首页 > 其他分享 >题解:P11249 [GESP202409 七级] 小杨寻宝

题解:P11249 [GESP202409 七级] 小杨寻宝

时间:2024-11-08 13:09:17浏览次数:3  
标签:ch 宝箱 GESP202409 int 题解 tr dep maxn P11249

题目显然等价于问所有宝箱是否在一条链上。

稍微转化一下题意,即我们现在要找到一条链,使得这条链上有宝物的节点数量尽可能多。

想到这里我们发现这个和树的直径比较相似,那么我们直接大胆将深度定义为从根到这个节点上有宝箱节点的数量,然后做一遍树的直径。最后判断直径长度是否等于所有有宝箱节点的数量即可。

做完以后我们发现这道题过了,其实证明也很简单。我们考虑把价值转到边上,即对于所有有宝箱的节点,让它所连的所有边长度都加上一。因为如果一条路径经过这条边,那么它一定也经过这个点,所以这样给边赋权后跑树的直径是对的,即上述思路正确。

Code

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long							
using namespace std;
//using namespace  __gnu_pbds;
//tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
//int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
//int findrank(int x){return tr.order_of_key(x)+1;}//查排名
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int maxn=3e5+10;
const int mod=998244353;
const int inf=1e9+7;
int n,a[maxn],dep[maxn];
vector<int> G[maxn];
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+(a[x]==1);
	for(auto y : G[x])
	{
		if(y==fa)continue;
		dfs(y,x);
	}
}
void Main()
{
	n=read();
	for(int i=1;i<=n;i++)dep[i]=0,G[i].clear();
	int sum=0;
	for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	int ma=-1,id=0;
	for(int i=1;i<=n;i++)
	{
		if(dep[i]>ma)
		{
			ma=dep[i];
			id=i;
		}
	}
	for(int i=1;i<=n;i++)dep[i]=0;
	dfs(id,0);
	ma=-1;
	for(int i=1;i<=n;i++)
	{
		ma=max(ma,dep[i]);
	}
	puts(ma==sum?"Yes":"No");
}
signed main()
{
#ifdef Lydic
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
	int T=read();
	while(T--)Main();
    return 0;
}

标签:ch,宝箱,GESP202409,int,题解,tr,dep,maxn,P11249
From: https://www.cnblogs.com/Lydic/p/18534854

相关文章

  • 题解:3254. 长度为 K 的子数组的能量值
    Problem:3254.长度为K的子数组的能量值I题解:3254.长度为K的子数组的能量值给定一个数组nums和一个整数k,我们需要找出所有长度为k的子数组的“能量值”。根据题意:如果子数组是连续递增的,能量值等于子数组中的最大元素。否则,能量值为-1。以下是两种不同......
  • CF 1365 题解
    CF1365题解AMatrixGame注意到每次操作都相当于会损失一行和一列,那么最多进行可用行列较少的那一个的轮数.判断奇偶性即可,BTroubleSort手玩发现,不管一个属性的元素集合内部多么无序,都可以借助一个其它属性的元素达到有序.归纳证明特别简单.因此,一个序列可以......
  • P5479 [BJOI2015] 隐身术 题解
    题目传送门前置知识后缀数组简介|字符串哈希|二分解法考虑分别计算出编辑距离恰好等于\(k_{0}\in[0,k]\)的答案。观察在编辑距离的存在下,长度差至多为\(k\)。考虑设\(f_{i,j}\)表示最大的\(x\)使得\(s_{1\simx}\)和\(t_{1\simx+j}\)可以在\(i\)次编......
  • P7984 [USACO21DEC] Tickets P 题解
    题目传送门前置知识线段树优化建图|最短路解法考虑对票建虚点,从\(c_{i}\)向\(i+n\)连一条权值为\(p_{i}\)的边,然后从\(i+n\)向\([a_{i},b_{i}]\)连一条权值为\(0\)的边。建出反图后\(1\toi\)和\(n\toi\)的路径集合会有重复统计的部分,不妨以\(dis_{1,i......
  • 快速上手Docker部署Flask项目 附常见问题解决
    一、准备Flask项目1.项目结构有一个app.py文件作为主应用程序入口,内容示例:fromflaskimportFlaskapp=Flask(__name__)@app.route('/')defhello_world():return'Hello,World!'if__name__=='__main__':app.run(host='0.0.0.0&#......
  • P9192 [USACO23OPEN] Pareidolia P 题解
    P9192[USACO23OPEN]PareidoliaP题解首先自然考虑不带修的情况。考虑问题的本质就是求序列中尽量短的bessie序列个数。对于尽量短的理解是对于bessiebessie序列,不考虑其由\(1,8\sim12\)构成的序列,只考虑\(1\sim6,7\sim12\)组成的序列。于是考虑dp:设\(dp_{i......
  • CF1956F Nene and the Passing Game 题解
    处理很妙的题,部分细节请教了未来姚班zyl和LYH_cpp,在此鸣谢。首先考虑把题目给的式子进行转化,设\(i<j\),那么\(i\)和\(j\)能传球当且仅当\(l_i+l_j\lej-i\ler_i+r_j\)。移项并拆开得到,\(i+l_i\lej-l_i\)且\(i+r_i\gej-r_j\),如果画到数轴上的话......
  • 题解:P11253 [GDKOI2023 普及组] 小学生数学题
    所求的式子带除法,模意义下除法计算复杂度带\(\log\)太慢了,先改写成乘法:\(\sum_{i=1}^ni!\timesi^{-k}\)。想求这个式子,最简单的思路就是对于每个整数\(i\in[1,n]\),分别预处理出\(i!\)和\(i^{-k}\)的值,最后乘起来再\(O(n)\)暴力加起来就好了!对于\(i!\),注意到:\[i!=\b......
  • P4621 [COCI2012-2013#6] BAKTERIJE 题解
    一道很好的数学题。首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是\(4\timesN\timesM\)。可以预处理每个细菌分别通过四个方向第一次到达终点的时间\(b_{i,0/1/2/3}\)和再次回到当前状态的循环节长度\(md_{i,0/1/2/......
  • 题解:[BZOJ2958] 序列染色
    ProblemLinkBZOJ2958序列染色题意给出一个长度为\(n\),由\(\ttB,W,X\)三种字符组成的字符串\(S\),你需要把每一个\(\ttX\)染成\(\ttB\)或\(\ttW\)中的一个。Solution字符串,染色,方案数,一眼\(dp\)。要求前半段是B,后半段是W。考虑容斥。\(f_{i,0/1},g_{i,......