题解

$$mx_u=min(now-b[u],\sum_{v\in son_u}mx_v+1)$$

$$mn_u=max(a[u],\sum_{v\in son_u}min_v)$$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<ctype.h>
#include<queue>
#include<map>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10000000
#define lowbit(x) (x & -x)
#define N 101005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
{
Re int x = 0; Re bool flag = 0; Re char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (flag) x = -x; return x;
}
struct edge {
int nxt, v;
} e[N << 1];
inline void addedge (int u, int v)
{
}
int now, mn[N], mx[N], a[N], b[N], A, B, sz[N];
bool flag;
inline void dfs (int u, int fa)
{
sz[u] = 1;
edge (i, u)
{
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}

mx[u] = 1; mn[u] = 0;
edge (i, u)
{
if (v == fa) continue;
mx[u] += mx[v];
mn[u] += mn[v];
}

mx[u] = std::min(mx[u], now - b[u]);
mn[u] = std::max(a[u], mn[u]);
if (mn[u] > mx[u] || mn[u] > now) flag = 0;
}
inline bool check ()
{
flag = 1;
dfs(1, 0);
return flag && mn[1] <= now && now <= mx[1];
}
int main ()
{
while (T--)
{
clr(head); clr(a); clr(b); tot = 0;
fo (i, 2, n)
{
}
while (A--)
{
}
while (B--)
{
}
int l = 0, r = n;
while (l < r)
{
now = l + r >> 1;
if (check()) r = now;
else l = now + 1;
}
now = l;
if (!check()) printf("-1\n");
else printf("%d\n", l);
}
return 0;
}