省队集训-0421模拟赛
allenchoi
·
·
个人记录
比赛链接
A.火力全开
题意：
有 n 只怪，m 个炸弹，给定常数 k。
第 i 个炸弹有代价 c_i，威力 d_i，每个炸弹至多使用一次；
第 i 只怪有血量 a_i，等级 b_i，杀死它要花 a_i 的代价普攻，或者引爆至少 k 个威力不小于 b_i 的炸弹。
$n,m,q\le 2.5\times 10^5,qk\le 5\times 10^5$。
#### Sol：
显然用恰好 $k$ 个炸弹或不用。把所有怪、炸弹按照 $b_i$ 或 $d_i$ 升序排序，则代价为一个后缀中 $a_i$ 之和，加上最小的 $k$ 个 $c_i$ 之和。
可以离线，将所有东西排好序后丢到一个线段树上，维护两个东西：$f1_{x,i}$ 表示 $x$ 子树内第 $i$ 小的 $c$，$f2_{x,i}$ 表示**后缀左端点在子树中**，且选了 $i$ 个 $c$ 时的最小代价。
显然第二维只用维护到 $k$。
pushup 时，$f1$ 归并排序即可，$f2$ 有转移：
$f2_{x,i}=\min(f2_{rs,i},\min\limits_{j} f2_{ls,j}+suma_{rs}+\sum\limits_{t=1}^{j}f1_{rs,t})$。
发现是一个卷积形式，所以可以做到 $O(qk^2\log)$，然后结合 $O(qn\log)$ 的暴力（枚举后缀）可以做到 $O(qk\sqrt{qk}\log)$。
进一步观察，发现 $\sum\limits_{t=1}^{j}f1_{rs,t}$ 有凸性，则它满足四边形不等式，所以 $j$ 对于 $i$ 有决策单调性，用二分队列即可做到 $O(k\log)$ 的 pushup。
**注意！！！** 最开始加入 $n+m$ 个点时不能用单调修改，否则复杂度会变成 $nk\log$ 不一定对。
总复杂度：$O((n+qk)\log^2)$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define il inline
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define ls (x << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
#define calc(j,i) (f2[ls][j] + s[i - j] + sum[rs])
using namespace std;
typedef long long ll;
const int N = 7.5e5 + 5,M = 1000;
const ll INF = 1e18;
int n,m,q,k,tot,id1[N],id2[N],pos[N],vis[N];
ll sum;
il int read()
{
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while('0' <= ch && ch <= '9') x = x * 10 + ch - '0',ch = getchar();
return x;
}
il void write(ll x,char ch)
{
int top = 0;
static int st[30];
while(x) st[++top] = x % 10,x /= 10;
for(int i = top;i >= 1;i--) putchar('0' + st[i]);
putchar(ch);
}
struct Node{int x,y,z,id;} p[N],opt[N];
bool cmp(Node x,Node y)
{
if(x.y != y.y) return x.y < y.y;
return x.z < y.z;
}
struct SgT
{
int cnt[N << 2],q[N],L[N],R[N];
ll sum[N << 2],s[N];
vector <int> f1[N << 2];
vector <ll> f2[N << 2];
void pushup(int x)
{
cnt[x] = cnt[ls] + cnt[rs],sum[x] = sum[ls] + sum[rs];
int u1 = min(cnt[ls],k),u2 = min(cnt[rs],k),u3 = min(cnt[x],k);
for(int i = 1,a = 1,b = 1;i <= u3;i++)
if(a <= u1 && (b > u2 || f1[ls][a] < f1[rs][b])) f1[x][i] = f1[ls][a++];
else f1[x][i] = f1[rs][b++];
for(int i = 0;i <= u3;i++) f2[x][i] = (i <= u2 ? f2[rs][i] : INF);
for(int i = 1;i <= u2;i++) s[i] = s[i - 1] + f1[rs][i];
int head = 1,tail = 0;
for(int i = 1,p1,p2,l,r,lim;i <= u3;i++)
{
while(head <= tail && R[head] < i) head++;
if(head <= tail) L[head] = i;
if(i <= u1)
{
lim = min(i + u2,u3);
while(head <= tail)
{
p1 = q[tail],p2 = L[tail];
if(calc(i,p2) < calc(p1,p2)) tail--;
else break;
}
if(head > tail) q[++tail] = i,L[tail] = i,R[tail] = lim;
else
{
l = L[tail],r = R[tail] + 1,p1 = q[tail];
while(r - l > 1)
{
p2 = mid;
if(calc(i,p2) < calc(p1,p2)) r = p2;
else l = p2;
}
R[tail] = l;
if(r <= lim) q[++tail] = i,L[tail] = r,R[tail] = lim;
}
}
if(head <= tail) p1 = q[head],f2[x][i] = min(f2[x][i],calc(p1,i));
}
}
int build(int x,int l,int r)
{
int ret;
if(l == r)
{
ret = p[l].z;
f1[x].resize(ret + 1),f2[x].resize(ret + 1);
if(vis[l])
if(!p[l].z) sum[x] = p[l].x;
else f1[x][1] = f2[x][1] = p[l].x,cnt[x] = 1;
return ret;
}
ret = min(build(ls,l,mid) + build(rs,mid + 1,r),k);
f1[x].resize(ret + 1);
f2[x].resize(ret + 1);
pushup(x);
return ret;
}
void update1(int x,int l,int r,int p,int v)
{
if(l == r)
{
sum[x] = v;
return ;
}
if(p <= mid) update1(ls,l,mid,p,v);
else update1(rs,mid + 1,r,p,v);
pushup(x);
}
void update2(int x,int l,int r,int p,int v)
{
if(l == r)
{
cnt[x] = (v > 0),f1[x][1] = f2[x][1] = v;
return ;
}
if(p <= mid) update2(ls,l,mid,p,v);
else update2(rs,mid + 1,r,p,v);
pushup(x);
}
} tr;
il void ins(int x)
{
if(!p[x].z) tr.update1(1,1,tot,x,p[x].x);
else tr.update2(1,1,tot,x,p[x].x);
}
il void ers(int x)
{
if(!p[x].z) tr.update1(1,1,tot,x,0);
else tr.update2(1,1,tot,x,0);
}
int main()
{
freopen("fire.in","r",stdin);
freopen("fire.out","w",stdout);
n = read(),m = read(),q = read(),k = read();
for(int i = 1;i <= n;i++) p[i].x = read(),p[i].y = read(),p[i].id = id1[i] = i,sum += p[i].x;
for(int i = 1;i <= m;i++) p[i + n].x = read(),p[i + n].y = read(),p[i + n].z = 1,p[i + n].id = id2[i] = i + n;
for(int i = 1;i <= q;i++)
{
opt[i].id = read() - 1,opt[i].x = read(),opt[i].y = read(),opt[i].z = read();
p[i + n + m] = (Node){opt[i].y,opt[i].z,opt[i].id,i + n + m};
}
tot = n + m + q;
sort(p + 1,p + tot + 1,cmp);
for(int i = 1;i <= tot;i++) pos[p[i].id] = i;
for(int i = 1;i <= n + m;i++) vis[pos[i]] = 1;
tr.build(1,1,tot);
for(int i = 1;i <= q;i++)
{
if(!opt[i].id) sum -= p[pos[id1[opt[i].x]]].x,sum += opt[i].y,ers(pos[id1[opt[i].x]]),ins(pos[id1[opt[i].x] = i + n + m]);
else ers(pos[id2[opt[i].x]]),ins(pos[id2[opt[i].x] = i + n + m]);
write(min(sum,(tr.cnt[1] >= k ? tr.f2[1][k] : INF)),'\n');
}
return 0;
}
~~~
### B.异或症测试 3
#### 题意：
给出 $n$ 个数 $s_i$ 和一个数 $X$，满足 $0\le s_i,X<2^m$，问有多少个 $[1,X]$ 的子集满足 $s$ 为它的最小线性基。
#### Sol：
定义对线性基消元，意思是通过基之间的相互异或，使得每个基都不含除自己代表的主元外的其它主元。称消元后的线性基为消元线性基。
设 $s$ 自己的线性基为 $p$，$p$ 能得到数集 $S$ 中，最大的不超过 $X$ 的数在 $S$ 中的排名为 $x$，则问题转换为 $[1,x]$ 中有多少子集 $T$ 的线性基大小为 $n$。其实这是将 $S$ 内的数与它的排名一一对应，而排名又只和它所含的主元有关，所以如果 $T$ 的线性基大小为 $n$，那就一定包含了 $p$ 内的所有主元，也就一定与 $p$ 相等。
$x$ 的话可以将 $p$ 消元，从大到小贪心地选。
不妨将全集改为 $[0,x]$。由于 $0$ 不影响线性基大小，所以最后把答案除以 $2$ 即可。
首先考虑怎么求出 $C_i$，表示 $[0,2^i)$ 的子集中线性基大小为 $i$ 的数量。
假设 $A\subseteq [0,2^i)$ 且线性基大小为 $i$，则将 $A$ 中的所有元素除以 $2$ 向下取整、去重得到集合 $B$，$B$ 的线性基的大小一定为 $i-1$。
由此延伸，考虑怎么用一个 $B$ 得到一个对应的 $A$。
首先如果 $x\in B$，则有 $2x\in A$，$2x+1\in A$ 和 $\set{2x,2x+1}\subseteq A$ 三种情况。
而有些情况得到的 $A$ 线性基大小为 $i-1$，考虑减去这些贡献。
观察到两个性质：
>1.如果 $A$ 的线性基大小为 $i-1$，那就是将 $B$ 的线性基内所有数乘上 $2$，然后最后一位乱填得到，这样的新线性基总共有 $2^{i-1}$ 种；
>
>2.显然 $2x,2x+1$ 不能同时属于 $A$，否则线性基含有 $1$，则大小为 $i$。
那么，如果我们确定了线性基 $A$，就可以确定 $2x,2x+1$ 中具体是那一个在 $A$ 中；同时，如果确定了 $i-2$ 个基末尾的填法，和 $2x/2x+1$ 的决策，也能定下唯一的一个基。
所以 $C_i=\sum\limits_B(3^{|B|}-2^{i-1})$。
其中 $3^|B|$ 表示每个 $x$ 的三种对应方式。
然后考虑上限 $x$。
设 $C_{i,0/1}$ 表示从高到低考虑了 $i$ 为，$x$ 前 $i$ 位的上限 $\left\lfloor\dfrac{x}{2^{n-i}}\right\rfloor$ 是否在集合内，$B_{0/1}$ 表示对应的集合。
考虑从 $i-1$ 转移到 $i$。分类讨论。
如果 $x$ 在 $n-i$ 位为 $0$：
如果 $x$ 在上一位的上限在 $B$ 内，那么它只能加上 $0$，并成为 $x$ 在这一位的上限；否则，$x$ 在这一位的上限一定不在 $A$ 里。所以：
$$C_{i,0}=\sum\limits_{B_0}(3^{|B_0|}-2^{i-1})$$
$$C_{i,1}=\sum\limits_{B_1}(3^{|B_1|-1}\times1-2^{i-2})$$
如果 $x$ 在 $n-i$ 位为 $1$：
如果 $x$ 在上一位的上限在 $B$ 内，那么它可以只加 $0$ 不成为上限，或加上 $1$ 成为上限；否则，$x$ 在这一位的上限一定不在 $A$ 里。所以：
$$C_{i,0}=\sum\limits_{B_0}(3^{|B_0|}-2^{i-1}+\sum\limits_{B_1}3^{|B_1|-1}\times1-2^{i-2})$$
$$C_{i,1}=\sum\limits_{B_1}(3^{|B_1|-1}\times 2^{i-2})$$
但是转移中有 $3^{|B|}$ 状的东西，很难处理，于是可以设 $G_{x,i,0/1}$ 表示 $\sum\limits_{B_{i,0/1}}x^{|B_{i,0/1}|}$。
前面 $3^{|B|}$ 意思是每个 $x$ 可以对应 $2x/2x+1$，加入一个元素，两种方案,以及而 $x$ 对应 $2x,2x+1$，加入两个元素，一种方案，所以应该改成：$\sum\limits_{j=0}^{|B|}\binom{|B|}{j}x^{j+2(|B|-j)}\times2^{j}=\binom{|B|}{j}(2x)^{j}\times(x^2)^{|B|-j}=(2x+x^2)^{|B|}$。
其它形如 $3^{|B|-1}\times1,3^{|B|-1}\times2$ 的式子也类似地修改，则得到转移式：
若上限 $x$ 的 $n-i$ 位为 $0$：
$$G_{x,i,0}=G_{x^2+2x,i-1,0}-2^{i-1}G_{x,i-1,0}$$
$$G_{x,i,1}=G_{x^2+2x,i-1,1}\times\frac{x}{x^2+2x}-2^{i-2}G_{x,i-1,1}$$
若上限 $x$ 的第 $n-i$ 位为 $1$：
$$G_{x,i,0}=G_{x^2+2x,i-1,0}-2^{i-1}G_{x,i-1,0}+G_{x^2+2x,i-1,1}\times\frac{x}{x^2+2x}-2^{i-2}G_{x,i-1,1}$$
$$G_{x,i,1}=G_{x^2+2x,i-1,1}\times\frac{x^2+x}{x^2+2x}-2^{i-2}G_{x,i,1}$$
令 $a_0=1,a_i={a_{i-1}}^2+2a_{i-1}$，$F_{x,i,0/1}=G_{a_x,i,0/1}$，则总状态数 $O(n^2)$，直接递推即可。
最后答案就是 $G_{1,n,0}+G_{1,n,1}=F_{0,n,0}+F_{0,n,1}$，记得除以 $2$。
Sol 写了快 1h（（（
#### Code：
~~~cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2010,mod = 998244353;
int n,m,cnt,ans,id[N],X[N],lim[N],a[N],inv[N],mi[N],f[N][N][2];
char ch[N];
bitset <N> v,p[N];
bool check(bitset <N> v)
{
for(int i = m - 1;i >= 0;i--) if(v[i] != X[i]) return (v[i] < X[i]);
return true;
}
int ksm(int x,int y)
{
int ret = 1;
while(y)
{
if(y & 1) ret = 1LL * ret * x % mod;
x = 1LL * x * x % mod,y >>= 1;
}
return ret;
}
int main()
{
freopen("basis.in","r",stdin);
freopen("basis.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
{
scanf("%s",ch + 1);
for(int j = 1;j <= m;j++) v[m - j] = ch[j] - '0';
for(int j = m - 1;j >= 0;j--)
{
if(!v[j]) continue;
if(!p[j].count())
{
p[j] = v;
break;
}
v ^= p[j];
}
}
scanf("%s",ch + 1);
for(int i = 1;i <= m;i++) X[m - i] = ch[i] - '0';
memset(id,-1,sizeof(id));
for(int i = 0;i < m;i++)
{
if(!p[i].count()) continue;
id[i] = cnt++;
for(int j = i + 1;j < m;j++) if(p[j][i]) p[j] ^= p[i];
}
v = 0;
for(int i = m - 1;i >= 0;i--)
{
if(id[i] == -1) continue;
if(check(v ^ p[i])) v ^= p[i],lim[id[i]] = 1;
}
if(!lim[n - 1])
{
puts("0");
return 0;
}
a[0] = 1;
for(int i = 1;i <= n;i++) a[i] = (1LL * a[i - 1] * a[i - 1] + 2 * a[i - 1]) % mod;
for(int i = 0;i <= n;i++) inv[i] = ksm(a[i],mod - 2);
for(int i = 0;i <= n;i++) f[i][1][1] = (1LL * a[i] * a[i] + a[i]) % mod;
mi[0] = 1;
for(int i = 1;i <= n;i++) mi[i] = 2 * mi[i - 1] % mod;
for(int i = 2;i <= n;i++)
if(!lim[n - i])
for(int j = 0;j <= n - i;j++)
{
f[j][i][0] = (f[j + 1][i - 1][0] - 1LL * mi[i - 1] * f[j][i - 1][0] % mod + mod) % mod;
f[j][i][1] = (1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * a[j] % mod - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
}
else
for(int j = 0;j <= n - i;j++)
{
f[j][i][0] = (f[j + 1][i - 1][0] - 1LL * mi[i - 1] * f[j][i - 1][0] % mod + mod) % mod;
f[j][i][0] = (f[j][i][0] + 1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * a[j] % mod) % mod;
f[j][i][0] = (f[j][i][0] - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
f[j][i][1] = 1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * (1LL * a[j] * a[j] % mod + a[j]) % mod;
f[j][i][1] = (f[j][i][1] - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
}
ans = 1LL * (f[0][n][0] + f[0][n][1]) * (mod / 2 + 1) % mod;
printf("%d\n",ans);
return 0;
}
~~~
### C.树上邻邻域数点
#### 题意：
交互题。给一棵大小为 $n$ 的树和常数 $L$，每个点有一个权值 $a_i\in[0,32)$。每次可以询问 $(x,d,v)$，表示距离 $x$ 恰好为 $d$ 的点中，$a_i\le v$ 的点数，要求 $d\ge L$。
$n=50000,L\le 2$，要求至多 $250000$ 次询问确定每个点的权值。保证树不是菊花。
#### Sol：
在值域上分治，每次确定 $a_i\in[l,r]$ 的点与 $mid$ 的关系（可以看作 $0/1$），不在分治区间内或已确定的点可以忽略掉。
考虑从下往上确定，如果一个点有孙子，则在孙子处问 $d=2$ 即可。
考虑其它情况。设这个点为 $x$，$x$ 的爷爷为 $f$，$f$ 的父亲为 $t$，$t$ 的父亲为 $g$。
考虑一次处理出 $g$ 子树内和 $x,f$ 同一层的所有点。
先处理有兄弟的 $x$。
如果 $f$ 的值确定了，则询问 $x$ 和它的所有兄弟 $d=2$ 的答案，如果值有两种，则较小的为 $1$，较大的为 $0$；否则全部的值都一样，根据总和和 $f$ 判断即可。
如果 $f$ 没确定，上面的方法也几乎可行，除了一种特殊情况：$x$ 只有一个兄弟 $y$，且两个查询的结果都是 $1$，此时有 $f=1,x=y=0$ 和 $f=0,x=y=1$ 两种情况。
如果 $f$ 子树内有没有兄弟的 $x$，直接问 $(x,2)$ 即可。其它情况，发现如果能求出 $f$ 的所有这类孙子（下称特殊点）的和就好了，这个等于 $(f,2)$，减去 $f$ 的所有兄弟和 $g$ 的值。如果 $f$ 的所有兄弟和 $g$ 都已经确定，后者可以直接得到；否则，先问一次 $(t,2)$，然后把 $f$ 的所有兄弟和 $g$ 中未确定的全部确定。注意到 $f$ 所有特殊点的和一定是偶数，而把减去“$f$ 的所有兄弟和 $g$ 的值”改成减去 $(t,2)$，最多会多减去 $1$，因此不会影响判断。
然后处理没有兄弟的 $x$。可以用 $(x,4)$ 和 $(f,2)$ 差分一下得到。
精细实现可以做到刚好 $n\log V$ 次，参考代码。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#include "tree.h"
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
typedef pair <int,int> pii;
namespace WORK
{
const int N = 50010;
int n,rt,dep[N],a[N],b[N],fa[N],p[N],d[N][5];
vector <int> v[N];
bool cmp(int x,int y){return dep[x] < dep[y];}
void dfs1(int x,int lst)
{
dep[x] = dep[lst] + 1;
for(int y : v[x]) if(y != lst) dfs1(y,x);
}
void dfs2(int x,int lst)
{
dep[x] = dep[fa[x] = lst] + 1;
if(lst) v[x].erase(find(v[x].begin(),v[x].end(),lst));
for(int y : v[x]) dfs2(y,x);
}
int qry(int x,int d,int v){return ask(x - 1,d,v);}
void upd(int x,int v)
{
b[x] = v;
for(int i = 0;i <= 4;i++) d[x][i] += v,x = fa[x];
}
void work1(int x,int sum,int tg,int mid)
{
for(int y : v[x])
{
vector <int> w;
for(int z : v[y]) if(b[z] == -1) w.pb(z);
if(w.size() == 1)
{
int z = w[0],c = qry(z,2,mid) - d[z][2] - d[y][1];
upd(x,c);
return ;
}
}
vector <int> k;
for(int y : v[x])
{
vector <int> w;
for(int z : v[y]) if(b[z] == -1) w.pb(z);
int m = (int)w.size();
if(!m) continue;
vector <int> C(m);
int c1 = -1,c2 = -1;
for(int i = 0;i < m;i++)
{
C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[y][1];
if(c1 == -1) c1 = C[i];
if(c1 != C[i]) c2 = C[i];
}
if(c2 != -1)
{
if(c1 > c2) swap(c1,c2);
for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
}
else if(m > 2 || c1 != 1)
for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
else k.pb(w[0]),k.pb(w[1]);
}
if(!tg && !k.size())
for(int y : v[x])
if(v[y].size())
{
int z = v[y][0];
upd(x,qry(z,2,mid) - d[z][2] - d[y][1] + d[z][0]);
return ;
}
int c = qry(x,2,mid) - d[x][2] - sum;
for(int i : k) upd(i,c > -tg);
upd(x,c <= -tg);
}
void work2(int x,int sum,int mid)
{
vector <int> k;
for(int y : v[x])
{
vector <int> w;
for(int z : v[y]) if(b[z] == -1) w.pb(z);
int m = w.size();
if(!m) continue;
if(m == 1)
{
k.pb(w[0]);
continue;
}
vector <int> C(m);
int c1 = -1,c2 = -1;
for(int i = 0;i < m;i++)
{
C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[y][1] - d[x][0];
if(c1 == -1) c1 = C[i];
if(c1 != C[i]) c2 = C[i];
}
if(c2 != -1)
{
if(c1 > c2) swap(c1,c2);
for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
}
else for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
}
if(!k.size()) return ;
int c = qry(x,2,mid) - d[x][2] - sum;
for(int i : k)
if(i == k.back()) upd(i,c);
else
{
int tmp = qry(i,4,mid) - d[i][4] - d[fa[i]][3] + d[i][2] - d[x][2] + d[fa[i]][1] - sum;
tmp = c - tmp,upd(i,tmp),c -= tmp;
}
}
void solve(int l,int r)
{
if(l == r) return ;
int mid = (l + r) / 2;
memset(d,0,sizeof(d));
for(int i = 1;i <= n;i++)
if(a[i] < l || a[i] > r) upd(i,a[i] < l);
else b[i] = -1;
for(int i = n;i >= 1;i--)
{
int x = p[i];
if(b[x] != -1) continue;
for(int y : v[x])
if(v[y].size())
{
int z = v[y][0];
upd(x,qry(z,2,mid) - d[z][2] - d[y][1] + d[z][0]);
break;
}
if(b[x] != -1) continue;
int f = fa[fa[x]],t = fa[f],g = fa[t];
vector <int> k;
for(int i : v[t]) if(i != f && b[i] == -1) k.pb(i);
if(b[g] == -1) k.pb(g);
int sum = 0;
if(k.empty())
{
sum = b[g];
for(int i : v[t]) if(i != f) sum += b[i];
if(b[f] == -1) work1(f,sum,0,mid);
sum += b[f];
}
else
{
sum = qry(f,2,mid);
for(int u : v[f])
{
vector <int> w;
for(int s : v[u]) if(b[s] == -1) w.pb(s);
if(w.empty()) continue;
int m = w.size();
if(m == 1)
{
int s = w[0],c = qry(s,4,mid) - d[s][4] - d[u][3] + d[s][2];
upd(s,sum - d[u][1] - c);
continue;
}
int c1 = -1,c2 = -1;
vector <int> C(m);
for(int i = 0;i < m;i++)
{
C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[u][1] - d[f][0];
if(c1 == -1) c1 = C[i];
if(c1 != C[i]) c2 = C[i];
}
if(c2 != -1)
{
if(c1 > c2) swap(c1,c2);
for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
}
else if(m > 2 || c1 != 1 || b[f] != -1)
for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
else
{
int s = w[0],c = qry(s,4,mid) - d[s][4] - d[u][3] + d[s][2];
c = sum - d[u][1] - c,upd(s,c > 0),upd(w[1],c > 0),upd(f,!c);
}
}
if(b[f] == -1) upd(f,qry(x,2,mid) - d[x][2] - d[fa[x]][1] + d[x][0]);
sum += b[f] - d[f][2];
for(int i : k)
if(i == k.back())
{
int c = sum;
for(int j : v[t]) if(i != j) c -= b[j];
if(i != g) c -= b[g];
upd(i,c);
}
else work1(i,sum,1,mid);
}
for(int i : v[t]) work2(i,sum - b[i],mid);
if(!t) work2(f,0,mid);
}
for(int i = 1;i <= n;i++) if(l <= a[i] && a[i] <= r) a[i] = (b[i] ? l : r);
solve(l,mid),solve(mid + 1,r);
}
vector <int> tree(int N,vector <pii> E,int M,int L)
{
n = N;
for(pii p : E) v[p.fi + 1].pb(p.se + 1),v[p.se + 1].pb(p.fi + 1);
dfs1(1,0);
for(int i = 1;i <= n;i++) if(dep[i] > dep[rt]) rt = i;
dfs2(rt,0);
for(int i = 1;i <= n;i++) p[i] = i;
sort(p + 1,p + n + 1,cmp);
solve(0,31);
vector <int> ret;
for(int i = 1;i <= n;i++) ret.pb(a[i]);
return ret;
}
}
vector <int> tree(int N,vector <pii> E,int M,int L){return WORK :: tree(N,E,M,L);}
~~~