点分治，用于快速统计一些树上路径问题的答案
对于点 \(u\) 将所有路径分为经过 \(u\) 的和 \(u\) 子树内的，每次在 \(u\) 的儿子中扫，合并得到 \(u\) 的子树中经过 \(u\) 的路径的答案，（计数类问题有时容斥），那么只要对所有点进行一遍这个过程就行了
考虑怎么选取 \(u\)，每次操作后需要对 \(u\) 的所有子树进行递归，每次取联通块的重心可以保证每条边尽可能被少访问从而保证复杂度
聪聪可可
被三整除的路径长度可以由两个被三整除的长度拼成，也可以是由余数相加被三整除的长度拼成，所以对每个点点分治的时候扫一遍深度，然后统计各种余数的数量，答案为 \(cnt_0^2+cnt_1*cnt_2*2\)，注意 \((u,u)\) 合法以及 \((u,v),(v,u)\) 不同
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
#define E 400005
ll n,t1,t2,t3,sum=0;
ll to[E],nx[E],w[E],h[N],tot=0;
inline void add(ll a,ll b,ll c){ to[++tot]=b; nx[tot]=h[a]; h[a]=tot; w[tot]=c; }
inline void link(ll a,ll b,ll c){ add(a,b,c); add(b,a,c); }
inline ll gcd(ll x,ll y){ return y?gcd(y,x%y):x; }
ll rt=0,mx[N],siz[N]; bool vis[N];
inline void getrt(ll u,ll f){
mx[u]=0; siz[u]=1;
for(int i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
getrt(to[i],u);
siz[u]+=siz[to[i]];
mx[u]=max(mx[u],siz[to[i]]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
ll dis[N],tmp[3];
inline void getdis(ll u,ll f){
tmp[dis[u]%3]++;
for(int i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
dis[to[i]]=(dis[u]+w[i])%3;
getdis(to[i],u);
}
}
inline ll cal(ll u,ll w){
tmp[0]=tmp[1]=tmp[2]=0;
dis[u]=w;
getdis(u,0);
return tmp[0]*tmp[0]+tmp[1]*tmp[2]*2;
}
ll ans=0;
inline void solve(ll u){
vis[u]=1; ans+=cal(u,0);
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]){
ans-=cal(to[i],w[i]);
sum=siz[to[i]]; rt=0; getrt(to[i],0);
solve(rt);
}
}
inline ll read(){
ll f=0,s=0; char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
int main(){
n=read();
for(int i=1;i<n;i++)t1=read(), t2=read(), t3=read()%3, link(t1,t2,t3);
sum=mx[rt=0]=n; getrt(1,0); solve(rt);
ll gc=gcd(ans,n*n);
printf("%lld/%lld",ans/gc,n*n/gc);
return 0;
}
[IOI2011]Race
做完这道感觉理解深刻了一些……
点分治骨架是四个函数，一个求重心，一个求子树答案，一个求点的答案，一个是分治的过程
求点的答案的函数中，枚举每个子树合并到当前答案中，每次处理完一个点记得清空
对于这个题，每个点维护当前扫过的子树中每个长度边数最小值即可
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
#define E 400005
#define K 1000005
#define inf 1000000000000
ll n,k,t1,t2,t3;
ll to[E],nx[E],h[N],w[E],tot=0;
inline void add(ll a,ll b,ll c){ to[++tot]=b; nx[tot]=h[a]; h[a]=tot; w[tot]=c; }
inline void link(ll a,ll b,ll c){ add(a,b,c); add(b,a,c); }
ll ans=inf,sum,rt;
ll mx[N],siz[N]; bool vis[N];
inline void getrt(ll u,ll f){
mx[u]=0; siz[u]=1;
for(int i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
getrt(to[i],u);
siz[u]+=siz[to[i]];
mx[u]=max(mx[u],siz[to[i]]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
ll ed[K],tmp[K],st1[K],tp1=0,st2[K],tp2=0;
ll dis[N];
inline void getdis(ll u,ll f,ll d){
if(dis[u]<K){
tmp[dis[u]]=min(tmp[dis[u]],d);
st1[++tp1]=dis[u];
}
for(int i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
dis[to[i]]=dis[u]+w[i];
getdis(to[i],u,d+1);
}
}
inline void div(ll u){
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]){
dis[to[i]]=w[i];
tp1=0; getdis(to[i],u,1);
for(int j=1;j<=tp1;j++){
if(k>=st1[j]&&k-st1[j]<K){
//cout<<k<<' '<<st1[j]<<' '<<tmp[st1[j]]<<' '<<ed[k-st1[j]]<<endl;
ans=min(ans,tmp[st1[j]]+ed[k-st1[j]]);
}
}
while(tp1){
if(ed[st1[tp1]]==inf)st2[++tp2]=st1[tp1];
ed[st1[tp1]]=min(ed[st1[tp1]],tmp[st1[tp1]]);
tmp[st1[tp1]]=inf,tp1--;
}
}
while(tp2){
ed[st2[tp2]]=inf;
tp2--;
}
}
inline void solve(ll u){
vis[u]=1; div(u);
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]){
rt=0; sum=mx[0]=siz[to[i]]; getrt(to[i],0);
solve(rt);
}
}
inline ll read(){
ll f=0,s=0; char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
int main(){
n=read(); k=read();
for(int i=1;i<n;i++)t1=read()+1,t2=read()+1,t3=read(),link(t1,t2,t3);
for(int i=1;i<K;i++)ed[i]=tmp[i]=inf;
mx[0]=sum=n; rt=0; getrt(1,0); solve(rt);
if(ans!=inf)printf("%lld",ans);
else puts("-1");
return 0;
}
Tree
统计小于等于 \(k\) 的，有两个思路：一是每个点容斥一下，二是每个点合并求，如果按第一种的话复杂度就 \(O(n^2\log n)\) 了……所以这时既然可以合并来做就这样吧……统计个数的过程可以用树状数组来做，总复杂度 \(O(n\log^2 n)\)
code:
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define N 40005
#define E 80005
#define rint register int
ll n,t1,t2,t3,k;
ll to[E],nx[E],w[E],h[N],tot=0;
inline void add(ll a,ll b,ll c){ to[++tot]=b; nx[tot]=h[a]; h[a]=tot; w[tot]=c; }
inline void link(ll a,ll b,ll c){ add(a,b,c); add(b,a,c); }
ll mn,siz[N],rt,sum=0; bool vis[N];
inline void getrt(ll u,ll f){
register int mx=0; siz[u]=1;
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]&&to[i]!=f){
getrt(to[i],u);
siz[u]+=siz[to[i]];
mx=max(mx,siz[to[i]]);
}
mx=max(mx,sum-siz[u]);
if(mx<mn)mn=mx,rt=u;
}
ll dis[N],tmp[N],tt=0;
ll st[N],tp=0;
inline void getdis(ll u,ll f){ //cout<<1;
if(dis[u]<=k){
st[++tp]=dis[u]; tmp[++tt]=dis[u];
}
else return;
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]&&to[i]!=f){
dis[to[i]]=dis[u]+w[i];
getdis(to[i],u);
}
}
ll v[N];
inline void upd(ll x,ll val){ for(rint i=x;i<=k;i+=i&-i)v[i]+=val; }
inline ll query(ll x){ if(x==0)return 0; ll res=0; for(rint i=x;i;i-=i&-i)res+=v[i]; return res; }
ll ans=0;
inline void div(ll u){
tp=0;
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]){
tt=0; dis[to[i]]=w[i]; getdis(to[i],u);
for(rint j=1;j<=tt;j++){
if(tmp[j]<=k)ans+=query(k-tmp[j]);
}
for(rint j=1;j<=tt;j++){
if(tmp[j]<=k)upd(tmp[j],1),ans++;
}
}
while(tp)if(st[tp]<=k)upd(st[tp],-1),tp--;
}
inline void solve(ll u){
vis[u]=1; div(u);
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]){
mn=sum=siz[to[i]]; rt=0; getrt(to[i],0);
solve(rt);
}
}
inline ll read(){
register ll f=0,s=0; register char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
int main(){
n=read();
for(rint i=1;i<n;i++)t1=read(), t2=read(), t3=read(), link(t1,t2,t3);
k=read();
mn=sum=n; rt=0; tp=0; getrt(1,0);
solve(rt);
printf("%d",ans);
return 0;
}
采药人的路径
感觉有点迷的一道题……
看到树上路径统计，想到点分治，可以把黑白设为 \(\pm 1\)，那么一段路径黑白相等即权值和为 \(0\)
如果只要求黑白相等的路径，就可以直接记录路径权值和放在桶里来查询
但是要求的是一个 能分成两段黑白相同的路径 的路径，所以在更新答案时，首先看这个点在这个正在加入的子树上是否有与他到分治点权值和相同的祖先，如果有那么已合并的子树里所有点都能和他们贡献答案，但如果没有，其他子树里就只有满足「在他被加入时所属的子树中 有祖先和他 至分治点的边权和 相等」的点能贡献答案，所以我们在更新桶时，把有边权和相同祖先的和没有的分两个桶统计
另外，如果一个点到分治点路径上黑白已经相等了，那么他是可以和他在这个子树中的满足同样条件的祖先一起贡献一条路径的答案的，我们只要记录每个边权和是否已经出现过就可以判断了
另外注意清空，栈清空在时间效率上有优势，但一定要注意把所有需要清空的都放到栈里，比如这题中初始化的编号也需要清空瞪着题解看半天没看懂，自己写完笔记发现会了
code:
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define N 200035
#define X 100005
#define E 200005
ll n,t1,t2,t3;
ll to[E],nx[E],h[N],w[E],tot=0;
inline void add(ll a,ll b,ll c){ to[++tot]=b; nx[tot]=h[a]; h[a]=tot; w[tot]=c; }
inline void link(ll a,ll b,ll c){ add(a,b,c); add(b,a,c); }
ll mx[N],siz[N],sum,rt; bool vis[N];
inline void getrt(ll u,ll f){
mx[u]=0; siz[u]=1;
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]&&to[i]!=f){
getrt(to[i],u);
siz[u]+=siz[to[i]];
mx[u]=max(mx[u],siz[to[i]]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
ll dis[N],p[N],q[N];
long long ans=0;//p:n q:y
ll buc[N];
inline void getdis(ll u,ll f){
if(buc[dis[u]+X])ans+=p[X-dis[u]];
ans+=q[X-dis[u]];
if(dis[u]==0)ans+=buc[X]>1;
buc[X+dis[u]]++;
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]&&to[i]!=f){
dis[to[i]]=dis[u]+w[i];
getdis(to[i],u);
}
buc[X+dis[u]]--;
}
ll st[N],tp=0;
ll ma=X,mi=X;
inline void getbuc(ll u,ll f){
ma=max(ma,dis[u]+X); mi=min(mi,dis[u]+X);
if(buc[dis[u]+X])q[dis[u]+X]++;
else p[dis[u]+X]++;
buc[dis[u]+X]++;
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]&&to[i]!=f)getbuc(to[i],u);
buc[X+dis[u]]--;
}
inline void div(ll u){
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]){
dis[to[i]]=w[i];
getdis(to[i],u);
getbuc(to[i],u);
}
}
inline void solve(ll u){
vis[u]=1; ma=mi=X; div(u);
memset(p+mi,0,(ma-mi+1)<<2); memset(q+mi,0,(ma-mi+1)<<2);
for(int i=h[u];i;i=nx[i])if(!vis[to[i]]){
rt=0; mx[0]=sum=siz[to[i]]; getrt(to[i],0); buc[X]=1;
solve(rt);
}
}
inline ll read(){
ll f=0,s=0; char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
int main(){
n=read();
for(int i=1;i<n;i++)t1=read(),t2=read(),t3=read(),link(t1,t2,t3*2-1);
rt=0; mx[0]=sum=n; getrt(1,0); buc[X]=1;
solve(rt);
printf("%lld",ans);
return 0;
}
[BJOI2017]树的难题
看到路径统计还有边数限制就大概是点分治了吧……
合并子树时讨论颜色是否相同，如果颜色相同需要减去一个颜色的贡献
写法有单调队列按秩合并和线段树合并
因为这个 \(\text{fw}\) 不会写单调队列所以只会线段树的 \(O(n \log^2 n)\) 做法……队爷们说单调队列按秩合并能少个 \(\log\)
感觉比想象中好写……其实点分治也是有一定格式的
线段树清空其实就是 \(rt,cnt\) 置 \(0\) 然后插新点时重设信息，所以不需要一个个暴力清空
code:
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rint register int
#define N 200005
#define E 400005
#define inf 2000000000
ll n,m,l,r,q[N],t1,t2,t3;
ll to[E],nx[E],w[E],h[N],tot=0;
inline void add(ll a,ll b,ll c){ to[++tot]=b; nx[tot]=h[a]; h[a]=tot; w[tot]=c; }
inline void link(ll a,ll b,ll c){ add(a,b,c); add(b,a,c); }
//---------------------------------------------------------------------------------
#define ls sl[x]
#define rs sr[x]
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
ll tr[N*100],sl[N*100],sr[N*100],cnt=0;
ll r1=0,r2=0;
inline void up(ll x){ tr[x]=max(tr[ls],tr[rs]); }
inline void ins(ll &x,ll l,ll r,ll p,ll val){
if(!x)x=++cnt,tr[x]=-inf,sl[x]=sr[x]=0;
if(l==r){ if(val!=-inf)tr[x]=max(val,tr[x]); else tr[x]=-inf; return; }
if(mid>=p)ins(lson,p,val); else ins(rson,p,val); up(x);
}
inline ll merge(ll x1,ll x2,ll l,ll r){
if(!x1||!x2)return x1+x2;
if(l==r){ tr[x1]=max(tr[x1],tr[x2]); tr[x2]=-inf; return x1; }
sl[x1]=merge(sl[x1],sl[x2],l,mid); sr[x1]=merge(sr[x1],sr[x2],mid+1,r); up(x1);
return x1;
}
inline ll query(ll x,ll l,ll r,ll nl,ll nr){
if(!x||nl>nr)return -inf;
if(nl<=l&&r<=nr)return tr[x]; ll res=-inf;
if(mid>=nl)res=max(res,query(lson,nl,nr)); if(mid<nr)res=max(res,query(rson,nl,nr));
return res;
}
inline void print(ll x,ll l,ll r){
if(l==r){
printf("%d: %d\n",l,tr[x]);
return;
}
if(ls)print(lson); if(rs)print(rson);
}
//---------------------------------------------------------------------------------
ll mx[N],siz[N],rt,sum; bool vis[N];
inline void getrt(ll u,ll f){
mx[u]=0; siz[u]=1;
for(rint i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
getrt(to[i],u);
siz[u]+=siz[to[i]];
mx[u]=max(mx[u],siz[to[i]]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
ll dis[N];
ll st[N],ec[N],tp=0,ed[N],tt=0;
inline void getdis(ll u,ll f,ll lc,ll d){
if(d<=r)st[++tp]=dis[u],ec[tp]=d;
else return;
for(rint i=h[u];i;i=nx[i])if(to[i]!=f&&!vis[to[i]]){
if(w[i]==lc)dis[to[i]]=dis[u];
else dis[to[i]]=dis[u]+q[w[i]];
getdis(to[i],u,w[i],d+1);
}
}
ll ans=-inf;
inline void div(ll u){ ll lc=0; cnt=0; r1=r2=0;
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]){
dis[to[i]]=q[w[i]]; getdis(to[i],u,w[i],1);
if(w[i]==lc){
for(rint j=1;j<=tp;j++){
if(ec[j]>r)continue;
ans=max(ans,query(r1,1,n,max(1,l-ec[j]),r-ec[j])+st[j]);
}
for(rint j=1;j<=tp;j++){
if(ec[j]>r)continue;
ans=max(ans,query(r2,1,n,max(1,l-ec[j]),r-ec[j])+st[j]-q[w[i]]);
}
}
else{
r1=merge(r1,r2,1,n);
for(rint j=1;j<=tp;j++){
if(ec[j]>r)continue;
ans=max(ans,query(r1,1,n,max(1,l-ec[j]),r-ec[j])+st[j]);
}
r2=0;
}
for(rint j=1;j<=tp;j++)if(ec[j]>=l&&ec[j]<=r)ans=max(ans,st[j]);
lc=w[i];
while(tp){
ins(r2,1,n,ec[tp],st[tp]);
tp--;
}
}
}
inline void solve(ll u){
vis[u]=1; div(u);
for(rint i=h[u];i;i=nx[i])if(!vis[to[i]]){
rt=0; mx[0]=sum=siz[to[i]]; getrt(to[i],0);
solve(rt);
}
}
struct node{
ll u,v,w;
inline bool operator<(const node &b)const{ return w>b.w; }
}ee[N];
inline ll read(){
ll f=0,s=0; char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
int main(){
n=read(); m=read(); l=read(); r=read(); tr[0]=-inf;
for(rint i=1;i<=m;i++)q[i]=read();
for(rint i=1;i<n;i++)ee[i].u=read(),ee[i].v=read(),ee[i].w=read();
sort(ee+1,ee+n);
for(rint i=1;i<n;i++)link(ee[i].u,ee[i].v,ee[i].w);
rt=0; mx[0]=sum=n; getrt(1,0);
solve(rt);
printf("%d",ans);
return 0;
}