题意
给定一棵 \(n\) 个节点的树，每个点有个喜欢程度。求 选联通块，并且这个联通块包含最大的点权的方案数。
分析
很难想的一道题……
原本思路：将权值最大的点设为根，跑一遍树形dp即可。
但是考虑到，权值最大的点可能不止一个，于是此做法失效。
考虑设\(dp_u\)表示在\(u\)的子树内，必定选取点\(u\)作为联通块，且包含最大点权的联通块个数。
使用树形dp，发现难以从子树中转移（因为最大点权的点可能不止一个）
于是考虑：使用补集转化思想，反向处理。
设f[u]表示以\(u\)的子树内所有联通块个数（必定选取\(u\)），\(g[u]\)为\(u\)的子树内不包含最大点权的联通块个数（必定选取\(v\)）。
则有：
\[f_u = \prod_{v\in son_u}(f_v+1)
\]
（对于每棵树，选取其子树\(v\)有\(f_v\)种，不选有\(1\)种）
同理，有：
\[g_u=\left\{\begin{matrix}
\prod_{v\in son_u} (g_v+1) , val_v \neq \max\\
0 , val_v = \max
\end{matrix}\right.
\]
则答案为：\(\sum (f_u-g_u)\).
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e5+5,mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=‘ ‘,c=getchar();
while(!(c>=‘0‘&&c<=‘9‘))ch=c,c=getchar();
while(c>=‘0‘&&c<=‘9‘)ret=(ret<<1)+(ret<<3)+c-‘0‘,c=getchar();
return ch==‘-‘?-ret:ret;
}
int n,m;
struct Edge{int to,nxt;}e[N<<1];
int head[N],ecnt = -1;
inline void add_edge(int u,int v){e[++ecnt] = (Edge){v,head[u]};head[u] = ecnt;}
ll a[N],mx=-1ll*INF*INF;
ll f[N],g[N];
ll ans;
void dfs(int u,int _f){
f[u] = 1 , g[u] = a[u] != mx;
for(int i = head[u] ; ~i ; i = e[i].nxt){
int v = e[i].to;
if(v == _f)continue;
dfs(v,u);
(f[u] *= f[v]+1) %= mod,
(g[u] *= g[v]+1) %= mod;
}
(ans += f[u]-g[u]+mod) %= mod;
}
signed main(){
memset(head,-1,sizeof(head));
n = read();
for(int i = 1 ; i <= n ; i ++)
a[i] = read(),
mx = max(a[i],mx);
for(int i = 1 ; i < n ; i ++){
int u = read() , v = read();
add_edge(u,v);add_edge(v,u);
}
dfs(1,0);
printf("%lld",ans);
}