[luogu] P1269 信号放大器 树形结构+贪心

前言

传送门 :

思路

一开始考虑是从哪个节点开始跑 , 结果没跑出来

仔细考虑一下,发现从哪个节点开始其实不重要 , 我们其实可以从叶子节点走到根节点

记录一下所走的距离,如果走的距离大于了当前的 k k k,那么 a n s + + ans++ ans++并且重置一下当前节点的 d i s dis dis即可

Mycode

const int N = 2e4+10;
struct node{
	int to,val;
};
vector g[N];
int n,k;
int total[N];
int ans;
int p[N];
int dis[N];

void dfs(int u,int fa){
	for(auto x : g[u]){
		if(x.to!=fa){
			p[x.to] = x.val;
			dfs(x.to,u);
			dis[u] = max(dis[u],dis[x.to]+x.val);
		}
	}
	
	if(dis[u]+p[u] >= k){
		++ans;
		dis[u] = 0 ;
		
	}
}

void solve(){
	cin>>n;
	
	int maxn = -1;
	
	for(int i=1;i>x;
		for(int j=1;j>a>>b;
			g[i].push_back({a,b});
			maxn = max(maxn,b);
		}
	}
	cin>>k;
	if(maxn >= k ){
		cout