小红的树上赋值(hard)
首先dfs可以把这颗树分为若干个块,对于每个块我们要使其和为0,且绝对值和最大,那么我们有什么办法确定填多少正数和负数,首先明确和为0,那么正数和负数填的绝对值和应该相同,那么我们只考虑正数,我们肯定填的越多越好,具体如何快速实现呢,这里有一个不是很明显的二分性,我们二分正数的值,判断凑出这个值需要的最少个数,这个块里的其他位置可以填负数,也可以为0,check一下是否满足,然后就可以完成了。注意对于块顶点不是红色的,我们填绝对值较大的那一个。当然出题人好像有一种贪心做法,可以去看一下回放。
int n, l, r;
int s1, s2;
bool st[N];
int ans[N];
vector<int> g[N];
int a[N], si[N];
bool check(int mid, int s)
{
int L = abs(l);
int x = (mid + r - 1) / r;
if (x > s)
return 0;
int y = s - x;
if (y * L >= mid)
return 1;
return 0;
}
void dfs(int u, int fa)
{
si[u] = 1;
for (auto ed : g[u])
{
if (ed == fa)
continue;
dfs(ed, u);
if (!a[ed])
si[u] += si[ed];
}
}
void dfs1(int u, int fa, int f)
{
st[u] = 1;
int t = 0;
if (f)
{
if (s1)
{
if (s1 >= r)
{
s1 -= r;
t = r;
}
else
{
t = s1;
s1 = 0;
}
ans[u] = t;
}
else if (s2)
{
if (s2 >= abs(l))
{
s2 -= abs(l);
t = abs(l);
}
else
{
t = s2;
s2 = 0;
}
ans[u] = -t;
}
else
ans[u] = 0;
}
else
{
if (r >= abs(l))
ans[u] = r;
else
ans[u] = l;
}
for (auto ed : g[u])
{
if (ed == fa || a[ed] || st[ed])
continue;
dfs1(ed, u, f);
}
}
void solve()
{
cin >> n >> l >> r;
string s;
cin >> s;
for (int i = 0; i < n; i++)
a[i + 1] = (s[i] == 'R');
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1, -1);
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
if (a[i])
{
int t = si[i];
int L = 0, R = 1e17;
while (L < R)
{
int mid = L + R + 1 >> 1;
if (check(mid, t))
L = mid;
else
R = mid - 1;
}
s1 = R, s2 = R;
dfs1(i, -1, 1);
}
else
dfs1(i, -1, 0);
}
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << ' ';
}
}