题意
给定一棵 (n) 个节点的树，每个点有个喜欢程度。求 选联通块，并且这个联通块包含最大的点权的方案数。
分析
很难想的一道题……
原本思路：将权值最大的点设为根，跑一遍树形dp即可。
但是考虑到，权值最大的点可能不止一个，于是此做法失效。
考虑设(dp_u)表示在(u)的子树内，必定选取点(u)作为联通块，且包含最大点权的联通块个数。
使用树形dp，发现难以从子树中转移（因为最大点权的点可能不止一个）
于是考虑：使用补集转化思想，反向处理。
设f[u]表示以(u)的子树内所有联通块个数（必定选取(u)），(g[u])为(u)的子树内不包含最大点权的联通块个数（必定选取(v)）。
则有：
[f_u = prod_{vin son_u}(f_v+1)
]
（对于每棵树，选取其子树(v)有(f_v)种，不选有(1)种）
同理，有：
[g_u=left{egin{matrix}
prod_{vin son_u} (g_v+1) , val_v
eq max\
0 , val_v = max
end{matrix}
ight.
]
则答案为：(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);
}