是时候总结一下树上差分一类题目的套路了。
树上差分
像差分一样，树上差分也有前缀和思想。
一个点的真实权值是一个点子树内所有差分后的权值之和总的来说就是一个点的差分数组最后的值是整个子树内差分数组的和，再加进点的权值里。
至于差分和前缀和的关系那就不必明说了。
树上差分可以分为两种（如果是一条链上都加 $1$）：
对于点的覆盖：
$u++$
$v++$
$LCA- -$
$fa[LCA]- -$
对于边的覆盖：
$u++$
$v++$
$LCA-=2$
之后就是例题：
点差分例题：
其实第一眼看上去这个名字我还以为是个网络流
点差分裸题，没有任何细节可言。
//#define LawrenceSivan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
const int maxn=5e4+5;
#define INF 0x3f3f3f3f
int n,k,maxx;
int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt;
inline void add(int u,int v){
nxt[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
int size[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn];
void dfs1(int u,int f){
size[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u])return;
dfs2(son[u],topf);
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int cntt[maxn];
void sum(int u,int f){
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
sum(v,u);
cntt[u]+=cntt[v];
}
}
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int main(){
#ifdef LawrenceSivan
freopen("aa.in","r",stdin);
freopen("aa.out","w",stdout);
#endif
n=read();k=read();
for(re int i=1,u,v;i<n;i++){
u=read();v=read();
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(re int i=1,s,t;i<=k;i++){
s=read();t=read();
int LCA=lca(s,t);
cntt[s]++;
cntt[t]++;
cntt[LCA]--;
cntt[fa[LCA]]--;
}
sum(1,0);
for(re int i=1;i<=n;i++){
maxx=max(maxx,cntt[i]);
}
printf("%d\n",maxx);
return 0;
}依然是点差分的裸题，只不过这一次有一些细节了。
唯一的细节是把即是起点也是终点的点算了两边。
最后减掉就行了。
//#define LawrenceSivan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=3e5+5;
const int maxm=1;
int n;
int a[maxn];
int head[maxn],fr[maxn<<1],to[maxn<<1],nxt[maxn<<1],cnt;
inline void add(int u,int v){
nxt[++cnt]=head[u];
fr[cnt]=u;
to[cnt]=v;
head[u]=cnt;
}
int dep[maxn],fa[maxn],son[maxn],top[maxn],size[maxn];
void dfs1(int u,int f){
fa[u]=f;
size[u]=1;
dep[u]=dep[f]+1;
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u])return;
dfs2(son[u],topf);
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(top[v])continue;
dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int cntt[maxn];
void sum(int u,int f){
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
sum(v,u);
cntt[u]+=cntt[v];
}
}
inline int read(){
int x=0, f=1;char ch=getchar();
while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int main() {
#ifdef LawrenceSivan
freopen("aa.in", "r", stdin);
freopen("aa.out", "w", stdout);
#endif
n=read();
for(re int i=1;i<=n;i++){
a[i]=read();
}
for(re int i=1,u,v;i<n;i++){
u=read();v=read();
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(re int i=1,u,v;i<n;i++){
u=a[i],v=a[i+1];
int LCA=lca(u,v);
cntt[u]+=1;
cntt[v]+=1;
cntt[LCA]-=1;
cntt[fa[LCA]]-=1;
}
sum(1,0);
for(re int i=2;i<=n;i++){
cntt[a[i]]--;
}
for(re int i=1;i<=n;i++){
printf("%d\n",cntt[i]);
}
return 0;
}
这个题就有点意思了。
题目简述：给定一棵树和 $m$ 个节点，然后给定一些路径，对于树上的点 $i$，问有多少路径的 从起点出发，经过 $w_j$ 以后恰好到达这个点。
首先第一反应也许是每一条路径一条一条看。
但是数据中显然有一条链的数据，于是 $O(nm)$的复杂度只能喝西北风。
于是可以考虑换一个角度。
我们能不能对于每一个点，看一看路径对他的贡献？
对于一个任意的路径 $s->t$ ，在树上显然地可以拆成 $s->LCA,LCA->t$，两个部分来看。
对于 $s->LCA$ 的路径，明显地可以发现，当这条路径对当前节点 $x$ 有贡献当且仅当 $dep[s]-dep[x]=w[x]$，通过移项得到 $dep[s]=dep[x]+w[x]$。
对于 $LCA->t$ 的路径，需要满足：$dep[s]+dep[x]-2 \times dep[LCA(s,t)]=w[x]$
依旧通过移项得到：$2 \times dep[LCA(s,t)]-dep[s]=dep[x]-w[x]$。
这里运用到了一种把 $s$ 关于 $LCA$ 翻上去的方法。其实这种思想小学或者初中就已经学过了
移项的手法是把带 $x$ 的都扔在一边，把已知的量扔在另一边。
于是这直接启示我们，可以在每个节点以 $dep$ 为下标进行统计。
之后对于 $s->LCA$ 路线，查询 $dep[x]+w[x]$ 出现多少次，对于 $LCA->t$ 路线，统计 $dep[x]-w[x]$ 出现多少次即可。
需要单点更改，单点查询。还要答案合并？
直接祭出线段树合并吧。
简单好写，思路清晰。
于是对于每一条路径，我们直接在起点位置的线段树 $dep[s]$ 下标 $++$，$LCA(s,t)$ 位置 $dep[s]$ 下标 $–$，在终点位置的线段树 $2 \times dep[LCA(s,t)]-dep[s]$ 下标 $++$，$fa[LCA]$位置 $2 \times dep[LCA(s,t)]-dep[s]$ 下标 $–$；
for(re int i=1,x,y;i<=m;i++){
x=read();y=read();
int LCA=lca(x,y);
modify(root[x],1,n<<1,n+dep[x],1);
modify(root[y],1,n<<1,n+2*dep[LCA]-dep[x],1);
modify(root[LCA],1,n<<1,n+dep[x],-1);
modify(root[fa[LCA]],1,n<<1,n+2*dep[LCA]-dep[x],-1);
}
最后合并线段树，然后上行路线查询 $dep[u]+w[u]$，下行路线查询 $dep[u]-w[u]$ 就可以了。
void dfs(int u){
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u])continue;
dfs(v);
root[u]=merge(root[u],root[v],1,n<<1);
}
if(w[u]&&n+dep[u]+w[u]<=(n<<1)){//判断越界
ans[u]+=query(root[u],1,n<<1,n+dep[u]+w[u]);//s->LCA
}
ans[u]+=query(root[u],1,n<<1,n+dep[u]-w[u]);//LCA->t
}需要注意的是，由于我们把 $s$ 关于 $LCA$ 翻上去的时候深度可能变成负数，所以我们可以直接把值域平移一下。
//#define LawrenceSivan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
const int maxn=3e5+5;
#define INF 0x3f3f3f3f
int n,m,w[maxn];
int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt;
inline void add(int u,int v){
nxt[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
namespace Tree_chain_partition{
int size[maxn],son[maxn],dep[maxn],fa[maxn],top[maxn];
void dfs1(int u,int f){
fa[u]=f;
size[u]=1;
dep[u]=dep[f]+1;
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u])return;
dfs2(son[u],topf);
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(top[v])continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
}
namespace SegmentTree{
#define ls st[rt].lc
#define rs st[rt].rc
int root[maxn],tot;
struct SegmentTree{
int lc,rc,v;
}st[maxn<<6];
void modify(int &rt,int l,int r,int pos,int val){
if(!rt)rt=++tot;
if(l==r){
st[rt].v+=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)modify(ls,l,mid,pos,val);
else modify(rs,mid+1,r,pos,val);
}
int query(int rt,int l,int r,int pos){
if(!rt)rt=++tot;
if(l==r)return st[rt].v;
int mid=(l+r)>>1;
if(pos<=mid)return query(ls,l,mid,pos);
else return query(rs,mid+1,r,pos);
}
int merge(int p,int q,int l,int r){
if(!p||!q)return p|q;
if(l==r){
st[p].v+=st[q].v;
return p;
}
int mid=(l+r)>>1;
st[p].lc=merge(st[p].lc,st[q].lc,l,mid);
st[p].rc=merge(st[p].rc,st[q].rc,mid+1,r);
return p;
}
}
using namespace Tree_chain_partition;
using namespace SegmentTree;
int ans[maxn];
void dfs(int u){
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u])continue;
dfs(v);
root[u]=merge(root[u],root[v],1,n<<1);
}
if(w[u]&&n+dep[u]+w[u]<=(n<<1)){
ans[u]+=query(root[u],1,n<<1,n+dep[u]+w[u]);//s->LCA
}
ans[u]+=query(root[u],1,n<<1,n+dep[u]-w[u]);//LCA->t
}
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
#define debug cout<<"warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
int main(){
#ifdef LawrenceSivan
freopen("aa.in","r",stdin);
freopen("aa.out","w",stdout);
#endif
n=read();m=read();
for(re int i=1,u,v;i<n;i++){
u=read();v=read();
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(re int i=1;i<=n;i++){
w[i]=read();
}
for(re int i=1,x,y;i<=m;i++){
x=read();y=read();
int LCA=lca(x,y);
modify(root[x],1,n<<1,n+dep[x],1);
modify(root[y],1,n<<1,n+2*dep[LCA]-dep[x],1);
modify(root[LCA],1,n<<1,n+dep[x],-1);
modify(root[fa[LCA]],1,n<<1,n+2*dep[LCA]-dep[x],-1);
}
dfs(1);
for(re int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}
边差分例题
这个题也挺好玩。
很容易就想到一个假思路。
直接找被经过次数最多的路径，然后删掉就行了。
错误性其实也很好想
如果有一条巨大的边权，比如 $1e3$，然后别的边都是 $1$，然后这个做法就直接没了。
于是重新审视这道题目：由于我们工作是同时开展的，于是所需要的总时间就是需要时间最长的那个。
于是要求删掉一条边以后最长的路径权值最小。
二分的模型？
然后自然而然地想到要二分这个值。
对于一条路，如果花费一段时间可以走完，那么如果给他更长的时间，他肯定也是可以走完的。
单调性显然。
于是可以二分去除这个边以后最大剩余路径的最小值。
并且需要判断，树上是否存在一条边，被比目前二分值更大的边全部覆盖。
然后我们需要找到需要被清除的边。
这条边理应是被所有大于等于当前二分值的路径都经过且长度尽量长的边。
int num[maxn],res,sum;
void get_sum(int u,int f){//树上前缀和统计经过次数
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
get_sum(v,u);
num[u]+=num[v];
}
if(num[u]==sum&&val[u]>res)res=val[u];//被所有大于mid的路径经过并且长度最长
}
inline bool check(int x){
memset(num,0,sizeof(num));
sum=res=0;
for(re int i=1;i<=m;i++){
if(q[i].d>x){
num[q[i].x]++;
num[q[i].y]++;
num[q[i].lca]-=2;
sum++;
}
}
get_sum(1,0);
if(road-res<=x)return true;//如果最长路径减去路径上最长的边可以比二分值更小，满足条件。
//容易想到，如果最长路径都可以，那么别的路径一定也可以
return false;
}
关于 $dis$（节点到根节点路径的边权和），用树上前缀和，树剖的时候顺便就搞出来了。
d(x,y)=dis[x]+dis[y]-2*dis[LCA(x,y)]
//#define LawrenceSivan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
const int maxn=3e5+5;
#define INF 0x3f3f3f3f
int n,m,Max,road;
int head[maxn],to[maxn<<1],nxt[maxn<<1],w[maxn<<1],cnt;
inline void add(int u,int v,int val){
nxt[++cnt]=head[u];
to[cnt]=v;
w[cnt]=val;
head[u]=cnt;
}
namespace Tree_chain_partition{
int size[maxn],dep[maxn],top[maxn],fa[maxn],son[maxn];
int dis[maxn],val[maxn],tot;
void dfs1(int u,int f){
size[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
val[v]=w[i];
dis[v]=dis[u]+w[i];
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u])return;
dfs2(son[u],topf);
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==son[u]||v==fa[u])continue;
dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
}
struct node{
int x,y,lca,d;
}q[maxn];
using namespace Tree_chain_partition;
int num[maxn],res,sum;
void get_sum(int u,int f){
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f)continue;
get_sum(v,u);
num[u]+=num[v];
}
if(num[u]==sum&&val[u]>res)res=val[u];
}
inline bool check(int x){
memset(num,0,sizeof(num));
sum=res=0;
for(re int i=1;i<=m;i++){
if(q[i].d>x){
num[q[i].x]++;
num[q[i].y]++;
num[q[i].lca]-=2;
sum++;
}
}
get_sum(1,0);
if(road-res<=x)return true;
return false;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int main(){
#ifdef LawrenceSivan
freopen("aa.in","r",stdin);
freopen("aa.out","w",stdout);
#endif
n=read();m=read();
for(re int i=1,u,v,val;i<n;i++){
u=read();v=read();val=read();
add(u,v,val);
add(v,u,val);
Max=max(Max,val);
}
dfs1(1,0);
dfs2(1,1);
for(re int i=1;i<=m;i++){
q[i].x=read();q[i].y=read();
q[i].lca=lca(q[i].x,q[i].y);
q[i].d=dis[q[i].x]+dis[q[i].y]-2*dis[q[i].lca];
road=max(road,q[i].d);
}
int l=road-Max,r=road;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
