P9386 [THUPC 2023 决赛] 大纲 题解
Larryyu
·
·
题解
Description
给定一棵有 n 个点的树和数列 a_1,a_2\dots a_n，若 a_i=-1 表示点 i 的值不确定，否则点 i 的值为非负整数 a_i。
你需要给每一个值不确定的点赋一个非负整数，使得该树满足以下条件：
- 设 maxn_x 表示点 x 的儿子中的最大值，若有多个儿子都为 maxn_x，则 x 的值为 maxn_x+1，否则 x 为 maxn_x。
问是否存在一组解，存在输出 Reasonable，不存在输出 Unreasonable。
Solution
对于一个点 i，如果其不确定，则它的初始取值下界为 0，上界为 1e9，如果确定，上界为 a_i，下界为 a_i，设 u_i 表示 i 的上界，b_i 表示 i 的下界。
遍历整棵树，对于点 x，求出儿子中最大的 b_{son_x}（也就是 maxn_x）以及数量 cnt 和最大的 u_{son_x}（设为 maxx_x，其实只有 1e9和 a_{son_x} 两种，也可以特判是否有不确定的点）。
由 $maxn_x$ 的定义得出，此时的 $maxn_x$ 还要再加上 $[cnt>1]$。
若 $a_x=-1$，更新上下界，满足条件，记住一定要更新上下界，第三个测试点 ```WA``` 的可能是因为这个。
若 $a_x\ne-1$，分类讨论：
- $a_x=maxn_x$，满足条件。
- $a_x<maxn_x$，下界都比当前大，绝对不满足条件。
- $a_x>maxn_x\ and\ a_x\le maxx_x$，虽然已经确定的儿子的下界取不到，但是儿子中还有不确定的，将其改为 $a_x$ 就满足条件了。
- $a_x>maxn_x\ and\ a_x>maxx_x$，不满足条件，因为儿子都确定了，所以无法改。
如此 ```dfs``` 即可。
## _Code_
```cpp
#include<bits/stdc++.h>
using namespace std;
#define inf 2000000000
int t;
int n;
int tot,head[100010];
int a[100010],b[100010],u[100010]; //a原数值，b下界，u上界
struct edge{
int to,next;
}e[200010];
void add(int x,int y){
e[++tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
void clean(){ //多测清空
tot=0;
for(int i=1;i<=n;i++){
head[i]=0;
}
}
bool dfs(int x,int fax){
int maxn=-10,cnt=0,maxx=-10;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fax) continue;
if(!dfs(y,x)) return 0; //儿子都已经不满足条件了，可以直接退出
if(b[y]>maxn){
maxn=b[y];
cnt=1;
}else if(b[y]==maxn){
cnt++;
}
maxx=max(maxx,u[y]);
}
if(maxn==-10){ //叶子节点
return 1;
}
maxn=maxn+(cnt>1);
if(a[x]!=-1){
if(a[x]<maxn) return 0;
else if(a[x]==maxn) return 1;
else if(a[x]<=maxx) return 1;
else return 0;
}
if(a[x]==-1){
u[x]=maxx;
b[x]=maxn;
return 1;
}
}
void solve(){
clean();
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==-1) u[i]=inf,b[i]=0;
else b[i]=u[i]=a[i];
}
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
if(dfs(1,0)) cout<<"Reasonable"<<endl;
else cout<<"Unreasonable"<<endl;
}
int main(){
cin>>t;
while(t--){
solve();
}
return 0;
}
```