题目
给一棵基环树，求树上路径长度 \(\ge k\) 的路径条数。
分析
点分治+基环树 \(Trick\)
首先基环树的一个基本处理办法就是先断掉一条环上的边，当成树处理后，再考虑这一条边的贡献。
这里就是必须经过这一条边的路径。
我们可以考虑这一条边的两端子树，显然就相当于拼接两条路径。
对于环上的每一个子树分开考虑，用 \(BIT\) 维护即可。
代码
实现裂开，只有 75 分。
75 分代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=2e5+5;
ll Ans;
int n,m,k;
int head[N],nex[N],to[N],idx=1;
inline void add(int u,int v){
nex[++idx]=head[u];
to[idx]=v;
head[u]=idx;
return ;
}
int Root,Size,FMax,siz[N];
bool vis[N],flag[N];
void GetRoot(int x,int fa){
siz[x]=1;int Max=0;
for(int i=head[x];i;i=nex[i]){
if(flag[i]) continue;
int y=to[i];
if(y==fa||vis[y]) continue;
GetRoot(y,x);siz[x]+=siz[y];
Max=max(Max,siz[y]);
}
Max=max(Max,Size-siz[x]);
if(Max<=FMax) FMax=Max,Root=x;
return ;
}
int c[N<<2];
inline void Add(int x,int v){
for(;x<=n*2;x+=(x&(-x))) c[x]+=v;
return ;
}
inline int Ask(int x){
int res=0;
for(;x;x-=(x&(-x))) res+=c[x];
return res;
}
int clear[N],cnt;
int Cnt,p[N];
void GetPathIn(int x,int fa,int D){
Add(D,1),clear[++cnt]=D;
for(int i=head[x];i;i=nex[i]){
if(flag[i]) continue;
int y=to[i];
if(y==fa||vis[y]) continue;
GetPathIn(y,x,D+1);
}
return ;
}
void GetPathOut(int x,int fa,int D){
Ans+=Ask(n)-Ask(max(1,k-D-1)-1);
for(int i=head[x];i;i=nex[i]){
if(flag[i]) continue;
int y=to[i];
if(y==fa||vis[y]) continue;
GetPathOut(y,x,D+1);
}
return ;
}
void DFS(int x){
vis[x]=true;cnt=0;
for(int i=head[x];i;i=nex[i]){
if(flag[i]) continue;
int y=to[i];
if(vis[y]) continue;
GetPathOut(y,x,1);
GetPathIn(y,x,1);
}
Ans+=Ask(n)-Ask(k-2);//加上本身就有的路径
for(int i=1;i<=cnt;i++) Add(clear[i],-1);
for(int i=head[x];i;i=nex[i]){
if(flag[i]) continue;
int y=to[i];
if(vis[y]) continue;
Root=y,FMax=Size=siz[y],GetRoot(y,x),y=Root,DFS(y);
}vis[x]=false;
return ;
}
int d[N],sta[N],top,top1,cl[N];
bool Insta[N];
void dfs(int x,int fa,int fr){
if(Insta[x]){
while(sta[top+1]!=x) cl[++top1]=sta[top--];
return flag[fr]=flag[fr^1]=true,void();
}
if(vis[x]) return ;
vis[x]=true;sta[++top]=x;Insta[x]=true;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==fa) continue;
dfs(y,x,i);
} top--;Insta[x]=false;
return ;
}
void Dfs1(int x,int fa,int D){
d[++top]=D;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==fa||vis[y]||flag[i]) continue;
Dfs1(y,x,D+1);
}
return ;
}
void Solve(){
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
for(int i=1;i<=top1;i++) vis[cl[i]]=true;
for(int i=1;i<=top1;i++){
top=0;
Dfs1(cl[i],0,0);
for(int j=1;j<=top;j++) Ans+=Ask(n)-Ask(max(1,k-(top1-i+1)-d[j])-1);
for(int j=1;j<=top;j++) Add(d[j]+i,1);
}
return ;
}
signed main(){
read(n),read(m),read(k);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
add(u,v),add(v,u);
}
if(m==n){
dfs(1,0,0);
memset(vis,0,sizeof(vis));
FMax=Size=n,Root=1,GetRoot(1,0),DFS(Root);
Solve();
}
else FMax=Size=n,Root=1,GetRoot(1,0),DFS(Root);
write(Ans);
return 0;
}
/*
5 4 2
1 3
2 4
3 5
4 1
*/
题解代码
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2e5 + 10;
const int mod = 1e9+7;
# define RG register
# define ST static
int n, m, K;
int head[M], nxt[M], to[M], tot=1; bool del[M];
inline void add(int u, int v) {
++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}
inline void adde(int u, int v) {
add(u, v), add(v, u);
}
ll ans = 0;
// ================== BIT =================== //
namespace BIT {
const int M = 6e5 + 10;
int c[M], n;
# define lb(x) (x&(-x))
inline void init(int _n) {
n = _n;
memset(c, 0, sizeof c);
}
inline void edt(int x, int d) {
for (; x<=n; x+=lb(x)) c[x] += d;
}
inline int sum(int x) {
int ret = 0;
for (; x; x-=lb(x)) ret += c[x];
return ret;
}
inline int sum(int x, int y) {
return sum(y) - sum(x-1);
}
# undef lb
}
// ================== dfz =================== //
int sz[M], mx[M];
bool vis[M];
inline void getsz(int x, int fa=0) {
sz[x] = 1, mx[x] = 0;
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || to[i] == fa || vis[to[i]]) continue;
getsz(to[i], x);
sz[x] += sz[to[i]];
if(sz[to[i]] > mx[x]) mx[x] = sz[to[i]];
}
}
int mi, centre;
inline void getcentre(int x, int tp, int fa=0) {
if(sz[tp] - sz[x] > mx[x]) mx[x] = sz[tp] - sz[x];
if(mx[x] < mi) mi = mx[x], centre = x;
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || to[i] == fa || vis[to[i]]) continue;
getcentre(to[i], tp, x);
}
}
inline void getans(int x, int d, int fa=0) {
ans += BIT::sum(max(1, K-d-1), n);
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || to[i] == fa || vis[to[i]]) continue;
getans(to[i], d+1, x);
}
}
inline void addans(int x, int d, int fa=0) {
BIT::edt(d, 1);
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || to[i] == fa || vis[to[i]]) continue;
addans(to[i], d+1, x);
}
}
inline void delans(int x, int d, int fa=0) {
BIT::edt(d, -1);
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || to[i] == fa || vis[to[i]]) continue;
delans(to[i], d+1, x);
}
}
inline void dfz(int x) {
getsz(x); mi = n;
getcentre(x, x);
x = centre;
// do something
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || vis[to[i]]) continue;
getans(to[i], 1, x);
addans(to[i], 1, x);
}
ans += BIT::sum(K-1, n);
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || vis[to[i]]) continue;
delans(to[i], 1, x);
}
vis[x] = 1;
for (int i=head[x]; i; i=nxt[i]) {
if(del[i] || vis[to[i]]) continue;
dfz(to[i]);
}
}
inline void solve_dfz() {
memset(vis, 0, sizeof vis);
BIT::init(n); dfz(1);
}
int st[M], stn, c[M], cn;
inline void dfs_circle(int x, int fa=0) {
if(cn) return;
if(vis[x]) {
for (int i=stn; st[i]!=x; --i) c[++cn] = st[i];
c[++cn] = x;
return ;
}
st[++stn] = x;
vis[x] = 1;
for (int i=head[x]; i; i=nxt[i]) {
if(to[i] == fa) continue;
dfs_circle(to[i], x);
}
--stn;
}
int d[M], dn=0;
inline void getdis(int x, int dis, int fa=0) {
d[++dn] = dis;
for (int i=head[x]; i; i=nxt[i]) {
if(to[i] == fa || del[i] || vis[to[i]]) continue;
getdis(to[i], dis+1, x);
}
}
inline void solve() {
stn = cn = 0;
dfs_circle(1);
// printf("%d\n", cn);
// for (int i=1; i<=cn; ++i) printf("%d ", c[i]);
// puts("");
for (int i=head[c[1]]; i; i=nxt[i]) {
if(to[i] == c[cn]) {
del[i] = 1; del[i^1] = 1;
break;
}
}
solve_dfz();
// cross c[cn]->c[1]
// printf("%lld\n", ans);
BIT::init(n);
memset(vis, 0, sizeof vis);
for (int i=1; i<=cn; ++i) vis[c[i]] = 1;
for (int i=1; i<=cn; ++i) {
dn = 0;
getdis(c[i], 0);
for (int j=1; j<=dn; ++j) ans += BIT::sum(max(1, K-(cn-i+1)-d[j]), n);
for (int j=1; j<=dn; ++j) BIT::edt(d[j]+i, 1);
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d%d", &n, &m, &K);
for (int i=1, u, v; i<=m; ++i) {
scanf("%d%d", &u, &v);
adde(u, v);
}
if(n == m) solve();
else solve_dfz(), printf("%lld\n", ans);
return 0;
}
/*
5 5 2
1 3
2 4
3 5
4 1
5 2
*/
感受
这道题相当于其他点分治多的就是基环树的那个处理套路，遇到基环树题就可以考虑这样的做法。