烟台做网站那家好/网络营销与直播电商学什么

题目

有一棵n(n<=1e5)个节点的树，树的每条边都有一个权值w，1号节点为根节点。

有q个机器人，第i个机器人有自己的权值xi。

第i个机器人从根节点出发，每次只走严格比xi小的权值最大的边。

求所有机器人最终停下来的节点的标号之和。

思路来源

https://www.cnblogs.com/ZGQblogs/p/10136243.html

题解

优先队列把机器人的权值都存进去，

每次按边权最大的搜，

回溯时如果机器人的权值大于该权值，说明可以留下

留下具体分两种情况，一种是这本身就是叶子结点

另一种是这是删掉机器人不能留下的权值最大的节点后，能留下的权值最大的叶子节点

如果没有留下，其实就相当于没有来过

正如迷宫回溯当且仅当该条路行不通一样，这里机器人回溯当且仅当当前搜索路径不可留

心得

调整搜索顺序是图论中的重要技巧鸭

往往用vector便于实现，链式前向星实在是不好排序

如CF1037D的D，调整bfs顺序，使之尽可能按给定序列的bfs序搜

再比如树链剖分，调整dfs顺序，先搜重儿子后搜轻儿子

本题中，调整dfs顺序，先搜与之相连的边权最大的儿子

有一种一堆考生优先去逛全国各名校，学霸留在了985，学渣说再去别的学校看看，结果留在了三本的感觉

后来考上三本的学渣矢口否认，没说自己考不上，说自己没去过985

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct node
{int v,w;node(){}node(int vv,int ww):v(vv),w(ww){}
};
bool cmp(node a,node b)
{return a.w>b.w;
}
vector<node>E[maxn];
priority_queue<int>q;
int T,N,Q;
int u,v,w,x;
ll ans;
//先搜大的边 询问更大的才能在这个点留下 否则搜不到这个点 
void dfs(int u,int fa,int maxw)//假设1有虚父亲之间有-1的边 不然无法处理留在1节点的边权询问 
{for(int i=0;i<E[u].size();++i){int v=E[u][i].v,w=E[u][i].w;if(v==fa)continue;dfs(v,u,max(w,maxw));}while(!q.empty()&&q.top()>maxw)//说明最大的会留在这里,或是叶子,或是砍掉上一个最大之后的叶子 {//printf("maxw:%d left:%d node:%d\n",maxw,q.size(),u);ans+=u;q.pop();} 
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&N,&Q);for(int i=1;i<=N;++i)E[i].clear();while(!q.empty())q.pop();for(int i=1;i<N;++i){scanf("%d%d%d",&u,&v,&w);//边是双向的 但可以在dfs时转化为有根树 E[u].push_back(node(v,w));E[v].push_back(node(u,w));}for(int i=1;i<=N;++i)//先搜权值大的 sort(E[i].begin(),E[i].end(),cmp);for(int i=1;i<=Q;++i){scanf("%d",&x);q.push(x);}ans=0;dfs(1,-1,-1);//dfs(当前节点,当前最大边权值) printf("%lld\n",ans);}return 0;
}