树初步 #1（插排串联 - 辽宁省2024CCPC）

树初步

数的基础内容可以看看树基础 - OI Wiki里面的讲解，对一些操作的基础概念介绍的很清楚；

下面直接来看例题：

插排串联 - 辽宁省CCPC

题目大意

给定一个n+1个节点的有根数；

根节点（0号）是插座，额定功率2200；

叶子节点是用电器，有运行的实际功率；

其他的中间节点都是插排，也会标有额定功率；

跟实际一样我们的实际功率不可以大于额定功率；我们可以调换中间插座的位置，看能否使这个树正常运行；

---

思路分析

利用DFS去遍历树，计算在每个插排的点的实际功率；然后利用贪心去安排每个地方的插排；最后看能否满足每个位置的实际功率都不超过额定功率；

遍历时记录所有用电器的和，不能超过根的2200；

这里的贪心我们可以先把所有插排的额定功率都先存起来，然后再把每个插排位置上的实际功率也存起来；

之后对两个数组进行排序；这样两个数组中的数会是一一对应的，我们就把小的分给小的大的分给大的，也就是遍历比较每一位，观察有没有超出额定的情况；如果有则说明怎么换都不能满足要求；

具体的操作思路在下面代码的注释中都有讲解

---

代码实现

看的时候先看主函数再去看dfs遍历的函数

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define push push_back
const int N=1e5+5;
vector<int>q[N],aa,bb; // 建立的树q，存额定的aa，记录实际的bb
map<int,int>mp;// 用来标记一下插排是那几个节点
int a[N];// 记录每个节点的值
int ss=0;// 记录所有用电器的总和
int dfs(int x){// 这里的x是节点的编号（下标）if(q[x].size()==0){// 遍历到叶子结点（用电器）ss+=a[x];// 将这个值累加return a[x];// 返回这个用电器的实际功率}int s=0;// 记录这个插排所连的点的功率和for(int i=0;i<q[x].size();i++){s+=dfs(q[x][i]); }bb.push(s);// 将这个插排处的实际功率记录到数组bb中return s;
}
void slove(){int n;cin>>n;for(int i=1;i<=n;i++){int u,v;cin>>u>>v;a[i]=v;// 存值q[u].push(i); //建树mp[u]++;// 标记插排}for(auto i:mp){aa.push(a[i.first]);// 遍历每个插排，将额定功率存起来}dfs(0);// DFS遍历树（0是插座是根节点所以从0开始遍历）if(ss>2200){ // 所有的和不能超过2200cout<<"NO";return;}bb.push(0);// 因为aa会把0这个根节点存进去，所以我们把bb前面也放入0来对齐数位，比较后面插排的匹配情况sort(aa.begin(),aa.end());sort(bb.begin(),bb.end());for(int i=0;i<aa.size();i++){if(aa[i]<bb[i]){// 实际功率超过了额定功率就不可以cout<<"NO";return;} }cout<<"YES";
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

---