题解：P14521 【MX-S11-T2】加减乘除
Lucyna_Kushinada
·
·
题解
Basic Observation
走到节点 $u$ 时，从根到 $u$ 路径上所有的点都会走过，记 $d_u=\sum_{x\in path_{1\to u}} a_x$，类似深度。
如果询问了一个 $x$，在 $u$ 节点时手上的数就是 $d_u+x$。
对于边 $(u,v,l,r)$，其中 $v$ 是 $u$ 的儿子，要走到 $v$ 有限制 $d_u+x\in [l,r]$，进而得出 $x\in [l-d_i,r-d_u]$，为什么想到这么做，因为后者是固定的值，前者是随询问变化的。
## Solution I
首先是重工业做法，将本题加强后也能做。
如果将 $x$ 看作时刻，那么可以将原问题转化为，给定一颗树，树边 $(u,v,l_x,r_x)$ 表示这条边仅在时刻 $\in[l_x,r_x]$ 时出现，$q$ 次询问，查询某一时刻根节点所在的连通块大小，鉴定为动态图连通性问题，不难想到线段树分治。
维护连通块大小可以用并查集，用按秩合并并查集结合线段树分治的结构，可以实现连通性的撤销，时间复杂度 $O(n\log^2 n+q\log n)$，能过。
```
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define sz(x) (int)(x).size()
#define N 500011
#define V 2000010
#define ll long long
// #define int long long
int n,m,fa[N],u[N],v[N];
ll a[N],d[N];
struct edge{
int t;
ll l,r;
};
struct node{
int u,v;
ll l,r;
};
vector<edge>e[N];
vector<ll>ve;
vector<node>ex;
vector<pair<ll,int>>g;
inline void dfs(int k){
d[k]=d[fa[k]]+a[k];
for(edge x:e[k]){
ll l=x.l-d[k],r=x.r-d[k];
if(l<=r){
ve.pb(l);
ve.pb(r);
ex.pb({k,x.t,l,r});
}
dfs(x.t);
}
}
int lim=0,ans[V];
namespace sol{
#define mid ((l+r)>>1)
vector<int>e[V<<2],que[V];
inline void ins(int k,int l,int r,int L,int R,int id){
if(L<=l&&R>=r){
e[k].pb(id);
return;
}
if(L<=mid){
ins(k*2,l,mid,L,R,id);
}
if(R>mid){
ins(k*2+1,mid+1,r,L,R,id);
}
}
struct dsu{
int fa[N],siz[N],tp;
pr st[N];
inline void init(){
rep(i,1,n){
fa[i]=i;
siz[i]=1;
}
}
inline int ask(int x){
while(x!=fa[x]){
x=fa[x];
}
return x;
}
inline bool mg(int x,int y){
x=ask(x),y=ask(y);
if(x==y){
return 0;
}
if(siz[x]>siz[y]){
swap(x,y);
}
fa[x]=y;
siz[y]+=siz[x];
st[++tp]={x,y};
return 1;
}
inline void recall(int pos){
while(tp>pos){
auto [x,y]=st[tp];
siz[y]-=siz[x];
fa[x]=x;
tp--;
}
}
}d;
inline void sol(int k,int l,int r){
int now=d.tp;
for(int i:e[k]){
d.mg(ex[i].u,ex[i].v);
}
if(l==r){
for(int i:que[l]){
ans[i]=d.siz[d.ask(1)];
}
d.recall(now);
return;
}
sol(k*2,l,mid);
sol(k*2+1,mid+1,r);
d.recall(now);
}
#undef mid
}
signed main(){
// freopen("calc.in","r",stdin);
// freopen("calc.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
rep(i,2,n){
ll l,r;
cin>>fa[i]>>l>>r;
e[fa[i]].pb({i,l,r});
}
rep(i,1,n){
char o;
cin>>o>>a[i];
if(o=='-'){
a[i]=-a[i];
}
}
dfs(1);
rep(i,1,m){
ll x;
cin>>x;
ve.pb(x);
g.pb({x,i});
}
sort(all(ve));
ve.erase(unique(all(ve)),ed(ve));
lim=sz(ve);
for(auto [x,i]:g){
x=lower_bound(all(ve),x)-bg(ve)+1;
sol::que[x].pb(i);
}
g.clear();
rep(i,0,sz(ex)-1){
auto [u,v,l,r]=ex[i];
l=lower_bound(all(ve),l)-bg(ve)+1;
r=lower_bound(all(ve),r)-bg(ve)+1;
sol::ins(1,1,lim,l,r,i);
}
ve.clear();
sol::d.init();
sol::sol(1,1,lim);
rep(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
## Solution II
在树上维护动态图连通性还是太魔怔了，现在是正常做法。
注意到询问的是根节点，只需要关于某个节点与根的连通性。
注意到树上两个节点之间的路径只有一条，那么走到 $u$ 就需要，询问的 $x$ 满足从根结点出发到 $u$ 路径上所有节点关于 $x$ 大小的限制，限制是可以预处理的。
注意到限制是区间，限制之间的合并就是区间求交，将根到 $u$ 路径上的所有限制**求交**作为 $u$ 的**新限制**，那么 $x$ 满足这个限制意味着根一定能到 $u$，而不仅仅只是 $u$ 与 $fa_u$ 之间的边在当前 $x$ 下存在。
那么可以对每个节点 $i$ 求出 $[p_i,q_i]$ 表示 $x$ 的取值范围，使得 $i$ 能与根连通。
离散化后做用差分实现区间加即可，时间复杂度 $O((n+q)\log n)$，瓶颈在于排序。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define sz(x) (int)(x).size()
#define N 500011
#define V 2000010
#define int __int128
int n,m,fa[N],u[N],v[N];
int a[N],d[N],ad[V];
pr b[N];
inline int rd(){
int x=0,f=1;
char c=0;
while(!isdigit(c)){
c=getchar_unlocked();
if(c=='-'){
f=-1;
}
}
while(isdigit(c)){
x=10*x+c-'0';
c=getchar_unlocked();
}
return x*f;
}
inline void out(int x){
if(x<0){
putchar_unlocked('-');
out(-x);
return;
}
if(x>9){
out(x/10);
}
putchar_unlocked(x%10+'0');
}
struct edge{
int t;
int l,r;
};
vector<edge>e[N];
vector<int>ve,que;
vector<pr>g;
bitset<N>f;
inline void dfs(int k,int L,int R){
d[k]=d[fa[k]]+a[k];
for(edge x:e[k]){
int l=max(x.l-d[k],L),r=min(x.r-d[k],R);
if(l<=r){
f[x.t]=1;
b[x.t].fi=l;
b[x.t].se=r;
ve.pb(l);ve.pb(r);
dfs(x.t,l,r);
}
}
}
int lim=0,ans[V];
signed main(){
// freopen("calc.in","r",stdin);
// freopen("calc.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
n=rd(),m=rd();
rep(i,2,n){
int l,r;
fa[i]=rd();
l=rd();r=rd();
e[fa[i]].pb({i,l,r});
}
rep(i,1,n){
char o;
cin>>o;
a[i]=rd();
if(o=='-'){
a[i]=-a[i];
}
}
dfs(1,-1e30,1e30);
rep(i,1,m){
int x=rd();
ve.pb(x);
que.pb(x);
}
sort(all(ve));
ve.erase(unique(all(ve)),ed(ve));
lim=sz(ve);
rep(i,1,n){
if(f[i]){
auto [l,r]=b[i];
l=lower_bound(all(ve),l)-bg(ve)+1;
r=lower_bound(all(ve),r)-bg(ve)+1;
ad[l]++;
ad[r+1]--;
}
}
rep(i,1,lim){
ad[i]+=ad[i-1];
}
for(int x:que){
x=lower_bound(all(ve),x)-bg(ve)+1;
out(ad[x]+1);
putchar_unlocked('\n');
}
return 0;
}
```