题解 P7043 【「MCOI-03」村国】
_zy_
·
·
题解
题目大意：
从这些点中找出最大的点，然后再在周围的点都加上1
。
------------
## 一些小小的性质：
很显然，如果直接按照题目中所说的那么很明显的会$T$飞（~~某位学长亲测~~）。
1. 很显然，手玩几个东西就会发现，其实就是两个点（哪两个点，先留个悬念）在那里跳啊跳啊，~~跳啊跳啊，我的骄傲放纵~~。
2. 那么具体怎么跳呢？
我们先找到一开始最优秀的点呀 。
- **最大的点中编号最小的点**。
emmm大概就是这样操作的。。。
```cpp
for(int i=1;i<=n;i++) {
a[i]=re();
if(a[i]>maxx) {
maxx=a[i];
now=i;
}
}
```
然后就建边先找到这个最大点的最大值的位置。
~~好了！悬念解开了!~~
没错就只需要看最大值的点和最大点的最大值点就好了呀。
因为+1+1+1只更新了这些点周围的点的好感值，所以最大点的最大值点是最有可能更新称为最大值。
关于这个点位置的处理
```cpp
int maxn=0; int k=0;
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(a[p]>maxn||(a[p]==maxn&&p<k)) {
maxn=a[p];
k=p;
}
}
```
----
#### 下面就是重头戏了嗷！！
1. 如果直接没有进循环，特判一手。
那么就是一个点了呀，直接输出这个点他不香吗，他香的一批!
#### 于是剩下的就是判断这两个最大点的最大点的最大值的差值就好了
2. 如果差值比$m$天大，就说明天数不够去让那个东西更新成为最大值。
——直接输出最大点就可以了.
3. 如果刚好相等呢？？？
刚好更新出来最大值，就要看编号了来比较，输出编号更小的那个就好了。
4. 如果更新到最大值之后，继续跳的时候。
如果奇数的话那么就跳到了这两个点编号更大的点。
偶数的时候就是另一个点了呀。
---
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define int long long
#define N 5000010
using namespace std;
int re() {
int p=0; char i=getchar();
while(i<'0'||i>'9') i=getchar();
while(i>='0'&&i<='9') p=p*10+i-'0',i=getchar();
return p;
}
int t,n,m,sum,now;
int a[N];
int fir[N],nex[N],poi[N];
void ins(int x,int y) { //某些大佬说不需要建边,我太菜了
nex[++sum]=fir[x];
poi[sum]=y;
fir[x]=sum;
}
void Clear() { //t次询问清0,建图只需要清空fir,sum记得清0
memset(fir,0,sizeof(fir));
memset(a,0,sizeof(a));
sum=0; now=0;
}
signed main()
{
t=re();
while(t--)
{
Clear();
n=re();m=re();
int maxx=0;
for(int i=1;i<=n;i++) {
a[i]=re();
if(a[i]>maxx) { //不能等于,因为这样才是编号最小的
maxx=a[i];
now=i;
}
}
for(int i=1;i<n;i++)
{
int a,b;
a=re();b=re();
ins(a,b); ins(b,a);
}
int maxn=0; int k=0;
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(a[p]>maxn||(a[p]==maxn&&p<k)) { 同上
maxn=a[p];
k=p;
}
}
if(k==0) {
printf("%lld\n",now);
continue;
}
int dat=maxx-maxn;
if(dat>m) {
printf("%lld\n",now);
continue;
}
if(dat==m) {
printf("%lld\n",min(now,k));
continue;
}
if((m-dat)&1) { //x&1判断是否是奇数
printf("%lld\n",max(now,k));
continue;
}
else {
printf("%lld\n",min(now,k));
continue;
}
}
return 0;
}
```
就酱，如果有什么不妥的地方，十分期望大家私信我
Orz