description:
给出一颗N个节点的树，边有边权。询问有多少条路径满足其长度小于等于给定值K
data range:
(N<=10^4)
solution:
点分治经典题目
考虑将一棵树的重心作为点分中心，对于子树内部的答案递归统计即可，在当前层我们只用考虑经过重心的路径
可以先统计从重心向外延伸形成的路径，然后再把它们两两拼接起来
至于具体的做法，可以排序后用双指针从两边往中间扫
还有就是注意在同一颗子树内的路径不能拼接在一起，要把这一部分减掉
另外单独考虑以重心为端点的路径
space time complexity:
时间：(O(nlogn))
空间：(O(n))
为什么时间是(O(nlogn))呢？
考虑每次选取重心以后整棵树的大小必然是其中最大子树大小的两倍
因此至多有(logn)层，每层复杂度都是(O(n)),总复杂度(O(nlogn))
code:
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=1e4+5,inf=1e9;
int N,K;
struct edge
{
int to,w;
edge(int _to=0,int _w=0){to=_to,w=_w;}
};
vector<edge>E[MAXN];
bool VIS[MAXN];
int getsz(int u,int pr)
{
int sz=1;
for(size_t i=0;i<E[u].size();++i)
{
const edge& v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
sz+=getsz(v.to,u);
}
return sz;
}
int fdrt(int u,int pr,int sz,int &rtsz,int &rt)
{
int mxs=-1,usz=1;
for(size_t i=0;i<E[u].size();++i)
{
const edge& v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
int chsz=fdrt(v.to,u,sz,rtsz,rt);
usz+=chsz,mxs=max(mxs,chsz);
}
mxs=max(mxs,sz-usz);
if(mxs<rtsz)rtsz=mxs,rt=u;
return usz;
}
inline int fdrt(int u)
{
int rtsz=inf,rt=-1,sz=getsz(u,0);
fdrt(u,0,sz,rtsz,rt);
return rt;
}
void getdis(int u,int pr,int d,vector<int>&ps)
{
if(d>K)return;
ps.push_back(d);
for(size_t i=0;i<E[u].size();++i)
{
const edge& v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
getdis(v.to,u,d+v.w,ps);
}
}
inline int work(vector<int>&ps)
{
int ans=0;
if(ps.empty())return 0;
sort(ps.begin(),ps.end());
for(size_t l=0,r=ps.size()-1;;++l)
{
while(l<r&&ps[l]+ps[r]>K)--r;
if(l>=r)break;
ans+=r-l;
}
return ans;
}
int solve(int u)
{
vector<int>len;int ans=0;
for(size_t i=0;i<E[u].size();++i)
{
const edge& v=E[u][i];
if(VIS[v.to])continue;
vector<int>ps;
getdis(v.to,u,v.w,ps);
ans-=work(ps);
len.insert(len.end(),ps.begin(),ps.end());
}
ans+=work(len)+len.size();
VIS[u]=true;
for(size_t i=0;i<E[u].size();++i)
{
const edge& v=E[u][i];
if(VIS[v.to])continue;
ans+=solve(fdrt(v.to));
}
return ans;
}
int main()
{
while(scanf("%d%d",&N,&K)==2&&N&&K)
{
for(int i=1;i<=N;++i)E[i].clear();
fill(VIS+1,VIS+N+1,false);
for(int i=1;i<N;++i)
{
int x,y,s;scanf("%d%d%d",&x,&y,&s);
E[x].push_back(edge(y,s));
E[y].push_back(edge(x,s));
}
printf("%d
",solve(fdrt(1)));
}
return 0;
}
UVA12161 铁人比赛 Ironman Race in Treeland
description:
给定N个点的树，边有两个权值：费用和长度。要求在所有费用不超过m的路径中找到最长的路径
data range:
(N<=3*10^4)
solution:
仿照上一道题的做法，当前只考虑经过重心的路径
类似地考虑从重心延伸出去的路径，用map记下所有路径所需的费用以及长度
然后再和先前得到的答案合并下，和双指针有些相似
再把当前得到的map合并进去就可以了
p.s.初始时要把(0,0)加入map，代表长度为0时费用也为0
space time complexity:
时间：(O(nlog^2n))
空间：(O(n))
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+5,inf=1e9;
typedef map<int,int> mii;
int T,N,M,KASE;
bool VIS[MAXN];
struct EDGE
{
int to,d,l;
EDGE(int _to=0,int _d=0,int _l=0){to=_to,d=_d,l=_l;}
};
vector<EDGE>E[MAXN];
int getsz(int u,int pr)
{
int sz=1;
for(int i=0;i<E[u].size();++i)
{
const EDGE &v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
sz+=getsz(v.to,u);
}
return sz;
}
int fdrt(int u,int pr,int sz,int &rtsz,int &rt)
{
int usz=1,mxs=-inf;
for(int i=0;i<E[u].size();++i)
{
const EDGE &v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
int vsz=fdrt(v.to,u,sz,rtsz,rt);
usz+=vsz,mxs=max(mxs,vsz);
}
mxs=max(mxs,sz-usz);
if(mxs<rtsz)rtsz=mxs,rt=u;
return usz;
}
inline int fdrt(int u)
{
int rtsz=inf,rt=-1,sz=getsz(u,-1);
fdrt(u,-1,sz,rtsz,rt);
return rt;
}
void dfs(int u,int pr,int d,int l,map<int,int>&mp)
{
if(d>M)return;
if(!mp.count(d))mp[d]=l;
else if(mp[d]<l)mp.erase(d),mp[d]=l;
for(int i=0;i<E[u].size();++i)
{
const EDGE &v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
dfs(v.to,u,d+v.d,l+v.l,mp);
}
}
inline int work(mii &ump,mii &vmp)
{
mii::iterator l=ump.begin();
mii::reverse_iterator r=vmp.rbegin();
int mx=-inf,ans=-inf;
for(;r!=vmp.rend();r++)
{
while(l!=ump.end()&&(l->first)+(r->first)<=M)
mx=max(mx,l->second),l++;
if(mx>0)ans=max(ans,mx+(r->second));
}
return ans;
}
int solve(int u)
{
int ans=-inf;mii ump;
for(int i=0;i<E[u].size();++i)
{
const EDGE &v=E[u][i];
if(VIS[v.to])continue;
mii vmp;vmp[0]=0;
dfs(v.to,u,v.d,v.l,vmp);
ans=max(ans,work(ump,vmp));
mii::iterator it=vmp.begin();
for(;it!=vmp.end();it++)
{
int d=it->first,l=it->second;
if(!ump.count(d))ump[d]=l;
else if(ump[d]<l)ump.erase(d),ump[d]=l;
}
}
VIS[u]=true;
for(int i=0;i<E[u].size();++i)
{
const EDGE &v=E[u][i];
if(VIS[v.to])continue;
ans=max(ans,solve(fdrt(v.to)));
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
fill(VIS+1,VIS+N+1,0);
for(int i=1;i<=N;++i)E[i].clear();
for(int i=1;i<N;++i)
{
int u,v,d,l;scanf("%d%d%d%d",&u,&v,&d,&l);
E[u].push_back(EDGE(v,d,l));
E[v].push_back(EDGE(u,d,l));
}
printf("Case %d: %d
",++KASE,solve(fdrt(1)));
}
return 0;
}
description:
给一棵树，每条边有权。求一条简单路径，权值和等于k，且经过的边的数量最小。
data range:
(N<=2*10^5) (k<=10^6)
solution:
感觉点分治的题都差不多啊（可能只是我题目做得太少了吧菜）
不过这题观察到k的范围比较小，可以直接开一个数组记下从重心出发长度为k所经过的最小边数
还有一个技巧，因为这个数组每次都要赋值为inf，所以每次都要重新赋值，这样可能会T
于是我们可以开一个rubbish数组记下修改了的点位，只要重新赋值这些点位就可以了
space time complexity:
时间：(O(nlogn))
空间：(O(n))
code:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=2e5+5,inf=1e9,MAXK=1e6+5;
int N,K,SZ[MAXN],LEN[MAXK];
struct edge{int to,w;edge(int _to=0,int _w=0){to=_to,w=_w;}};
vector<edge>E[MAXN];
bool VIS[MAXN];
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
int fdrt(int u,int pr,int sz,int &rtsz,int &rt)
{
int mxs=-inf,&usz=SZ[u];usz=1;
for(int i=0;i<E[u].size();++i)
{
const edge &v=E[u][i];
if(VIS[v.to]||v.to==pr)continue;
usz+=fdrt(v.to,u,sz,rtsz,rt);
mxs=max(mxs,SZ[v.to]);
}
mxs=max(mxs,sz-usz);
if(mxs<rtsz)rtsz=mxs,rt=u;
return usz;
}
inline int fdrt(int u,int sz)
{
int rtsz=inf,rt=-1;
fdrt(u,0,sz,rtsz,rt);
return rt;
}
void dfs(int u,int pr,int w,int cnt,vector<pii>&p)
{
if(w>K)return;
p.push_back(make_pair(w,cnt));
for(int i=0;i<E[u].size();++i)
{
const edge &v=E[u][i];
if(v.to==pr||VIS[v.to])continue;
dfs(v.to,u,w+v.w,cnt+1,p);
}
}
inline int work(vector<pii>&p)
{
int ans=inf;
for(int i=0;i<p.size();++i)
ans=min(ans,LEN[K-p[i].first]+p[i].second);
return ans;
}
int solve(int u)
{
LEN[0]=0;
int ans=inf;vector<int>rubbish;
for(int i=0;i<E[u].size();++i)
{
const edge &v=E[u][i];
if(VIS[v.to])continue;
vector<pii>p;p.push_back(make_pair(0,0));
dfs(v.to,u,v.w,1,p);
ans=min(ans,work(p));
for(int i=0;i<p.size();++i)
LEN[p[i].first]=min(LEN[p[i].first],p[i].second),
rubbish.push_back(p[i].first);
}
VIS[u]=1;
for(int i=0;i<rubbish.size();++i)LEN[rubbish[i]]=inf;
for(int i=0;i<E[u].size();++i)
{
const edge &v=E[u][i];
if(VIS[v.to])continue;
ans=min(ans,solve(fdrt(v.to,SZ[v.to])));
}
return ans;
}
int main()
{
N=read(),K=read();
fill(LEN+1,LEN+K+1,inf);
for(int i=1;i<N;++i)
{
int u=read()+1,v=read()+1,s=read();
E[u].push_back(edge(v,s));
E[v].push_back(edge(u,s));
}
int ans=solve(fdrt(1,N));
printf("%d
",ans>=inf?-1:ans);
return 0;
}
UVA1674 闪电的能量 Lightning Energy Report
description:
树上要求支持链加，单点求值
solution:
直接上树链剖分套个线段树就可以了
p.s.不过比直接树上差分复杂多了。。。
space time complexity:
时间：(O(nlog^2n))
空间：(O(n))
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
int K,N,CNT;
int FA[MAXN],TOP[MAXN],HS[MAXN],ID[MAXN],DEP[MAXN];
vector<int>E[MAXN];
struct Segtree
{
int tag[MAXN<<2];
#define lc rt<<1
#define rc rt<<1|1
inline void cler(){memset(tag,0,sizeof(tag));}
inline void down(int rt)
{
int &tg=tag[rt];
if(!tg)return;
tag[lc]+=tg,tag[rc]+=tg;
tg=0;
}
void upd(int rt,int ll,int rr,int c,int l=1,int r=N)
{
if(ll<=l&&r<=rr){tag[rt]+=c;return;}
down(rt);
int mid=l+r>>1;
if(ll<=mid)upd(lc,ll,rr,c,l,mid);
if(mid<rr)upd(rc,ll,rr,c,mid+1,r);
}
int query(int rt,int p,int l=1,int r=N)
{
if(l==r)return tag[rt];
down(rt);
int mid=l+r>>1;
if(p<=mid)return query(lc,p,l,mid);
else return query(rc,p,mid+1,r);
}
#undef lc
#undef rc
}T;
int dfs1(int u,int pr)
{
DEP[u]=DEP[pr]+1,FA[u]=pr,HS[u]=0;
int sz=1,mxs=-1;
for(int i=0;i<E[u].size();++i)
{
int v=E[u][i];
if(v==pr)continue;
int vsz=dfs1(v,u);sz+=vsz;
if(vsz>mxs)mxs=vsz,HS[u]=v;
}
return sz;
}
void dfs2(int u,int top)
{
TOP[u]=top,ID[u]=++CNT;
if(HS[u])dfs2(HS[u],top);
for(int i=0;i<E[u].size();++i)
{
int v=E[u][i];
if(v!=FA[u]&&v!=HS[u])dfs2(v,v);
}
}
void upd(int x,int y,int c)
{
while(TOP[x]!=TOP[y])
{
if(DEP[TOP[x]]<DEP[TOP[y]])swap(x,y);
T.upd(1,ID[TOP[x]],ID[x],c);
x=FA[TOP[x]];
}
if(ID[x]>ID[y])swap(x,y);
T.upd(1,ID[x],ID[y],c);
}
int main()
{
scanf("%d",&K);
for(int kase=1;kase<=K;++kase)
{
scanf("%d",&N);
T.cler();CNT=0;
for(int i=1;i<=N;++i)E[i].clear();
for(int i=1;i<N;++i)
{
int x,y;scanf("%d%d",&x,&y);++x,++y;
E[x].push_back(y);
E[y].push_back(x);
}
dfs1(1,0);dfs2(1,1);
int q;scanf("%d",&q);
while(q--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
upd(++a,++b,c);
}
printf("Case #%d:
",kase);
for(int i=1;i<=N;++i)printf("%d
",T.query(1,ID[i]));
}
return 0;
}
description:
要求支持子树、链修改，子树、链查询
solution:
直接上树链剖分套个线段树就可以了
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
vector<int>e[N];
struct Segtree
{
int s1[N<<2],len[N<<2],tag[N<<2];
#define lc rt<<1
#define rc rt<<1|1
inline void up(int rt){s1[rt]=s1[lc]+s1[rc];}
inline void down(int rt)
{
int &tg=tag[rt];
if(tg==-1)return;
tag[lc]=tag[rc]=tg;
s1[lc]=tg?len[lc]:0,s1[rc]=tg?len[rc]:0;
tg=-1;
}
void build(int rt,int l,int r)
{
len[rt]=r-l+1,tag[rt]=-1,s1[rt]=0;
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
void upd(int rt,int ll,int rr,int c,int l=1,int r=n)
{
if(ll<=l&&r<=rr)
{
s1[rt]=c?len[rt]:0,tag[rt]=c;
return;
}
down(rt);
int mid=l+r>>1;
if(ll<=mid)upd(lc,ll,rr,c,l,mid);
if(mid<rr)upd(rc,ll,rr,c,mid+1,r);
up(rt);
}
int query(int rt,int ll,int rr,int l=1,int r=n)
{
if(ll<=l&&r<=rr)return s1[rt];
down(rt);
int mid=l+r>>1,anss=0;
if(ll<=mid)anss+=query(lc,ll,rr,l,mid);
if(mid<rr)anss+=query(rc,ll,rr,mid+1,r);
up(rt);
return anss;
}
#undef lc
#undef rc
}T;
struct HLD
{
int cnt;
int fa[N],sz[N],dep[N],top[N],id[N],hs[N];
void dfs1(int u,int pr)
{
dep[u]=dep[pr]+1;fa[u]=pr;
sz[u]=1;int mxs=-1;
for(int i=0;i<e[u].size();++i)
{
int &v=e[u][i];
dfs1(v,u);sz[u]+=sz[v];
if(sz[v]>mxs)mxs=sz[v],hs[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp,id[u]=++cnt;
if(hs[u])dfs2(hs[u],tp);
for(int i=0;i<e[u].size();++i)
{
int &v=e[u][i];
if(v!=hs[u])dfs2(v,v);
}
}
void upd(int x,int y,int c)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
T.upd(1,id[top[x]],id[x],c);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
T.upd(1,id[x],id[y],c);
}
int query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=T.query(1,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans+=T.query(1,id[x],id[y]);
return ans;
}
}hld;
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;++i)
{
int pr;scanf("%d",&pr);++pr;
e[pr].push_back(i);
}
hld.dfs1(1,0),hld.dfs2(1,1);
T.build(1,1,n);
int q;scanf("%d",&q);
while(q--)
{
char ch[20];int x;
scanf("%s%d",ch,&x);++x;
if(ch[0]=='i')
printf("%d
",hld.dep[x]-hld.query(1,x)),hld.upd(1,x,1);
else
printf("%d
",T.query(1,hld.id[x],hld.id[x]+hld.sz[x]-1)),
T.upd(1,hld.id[x],hld.id[x]+hld.sz[x]-1,0);
}
return 0;
}