Steven_MengのBlog

这题其实就是点分治的一个扩展。

首先,对于一棵树的情况,可以想到点分治:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int stk[MAXN],top;
void Koko(int u,int father,int dep){
stk[++top]=dep;
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father&&!vis[v]){
Koko(v,u,dep+1);
}
}
}
long long Calc(int u,int w){
top=0;
Koko(u,0,w);
sort(stk+1,stk+1+top);
long long ans=0;
for (int i=1;i<=top;++i){
int pos=lower_bound(stk+1,stk+1+top,k-stk[i]-1)-stk-1;
ans+=top-pos;
}
return ans;
}

对于一个stk[i],只有小于等于k-stk[i]-1stk[j]是不合法的,于是减去即可。

这样可以$O(n \log ^2 n)$做出一棵树的情况。

再考虑基环树:

可以先删除环上的一条边$(u,v)$,变成一棵树的情况,套用上面的算法算出路径数,这样算出的是不含$(u,v)$的路径数,于是还要算出包含$(u,v)$的路径数。

jh.png

考虑顺时针搞过去,每来一个子树,查询跨过$(u,v)$,即继续顺时针走过去的方案数。

然后加入这个子树即可。

注意代码中我们维护的是到$u$的距离,于是转化为$dis(p,q) \ge k-1$,需要注意一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,m,k;
namespace DFZ{
vector<int>G[MAXN];
void AddEdge(int u,int v){
G[u].push_back(v);
}
int sz[MAXN],Max[MAXN],centre;
int vis[MAXN];
void Find(int u,int father,int treesz){//找重心
sz[u]=1,Max[u]=0;
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v&&v!=father&&!vis[v]){
Find(v,u,treesz);
sz[u]+=sz[v];
Max[u]=max(Max[u],sz[v]);
}
}
int up=treesz-sz[u];
Max[u]=max(Max[u],up);
if (Max[u]<Max[centre]) centre=u;
}
int stk[MAXN],top;
void Koko(int u,int father,int dep){
stk[++top]=dep;
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v&&v!=father&&!vis[v]) Koko(v,u,dep+1);
}
}
long long Calc(int u,int w){
top=0;
Koko(u,0,w);
sort(stk+1,stk+1+top);
long long ans=0;
for (int i=1;i<=top;++i){
int pos=lower_bound(stk+1,stk+1+top,k-stk[i]-1)-stk-1;
ans+=top-pos;
}
return ans;
}
long long ret=0;
int GetCentre(int u,int sz){
centre=0;
Find(u,0,sz);
return centre;
}
void dfs(int u){
vis[u]=true;
ret+=Calc(u,0);
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v&&!vis[v]){
ret-=Calc(v,1);
dfs(GetCentre(v,sz[v]));
}
}
}
}
using namespace DFZ;
void SolveTree(){
dfs(GetCentre(1,n));
printf("%lld\n",ret/2ll);
}
bool flag;
int fa[MAXN],U,V,t;
void FindCircle(int u,int father){
if (flag) return ;
fa[u]=father;
if (vis[u]){
t=u;
flag=true;
return ;
}
vis[u]=true;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v==father) continue;
FindCircle(v,u);
}
}
vector<int>Circle;//在环上的点
namespace BIT{
int C[MAXN*2];
#define lowbit(i) i&(-i)
void Add(int k,int val){
k+=MAXN;
for (int i=k;i>0;i-=lowbit(i)) C[i]+=val;
}
int Ask(int k){
k+=MAXN;
int ans=0;
for (int i=k;i<MAXN*2;i+=lowbit(i)) ans+=C[i];
return ans;
}
}
using namespace BIT;
int Mark[MAXN];//Mark一下环上的点
//维护的是到t点的距离
void QuerySubtree(int u,int father,int w){//原本的深度
ret+=Ask(k-w-1);
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v&&v!=father&&!Mark[v]) QuerySubtree(v,u,w+1);
}
}
void AddSubtree(int u,int father,int w){
Add(w,1);
for (int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v&&v!=father&&!Mark[v]) AddSubtree(v,u,w+1);
}
}
void SolveJHTree(){
FindCircle(1,1);
memset(vis,0,sizeof(vis));
U=t,V=fa[t];//删掉<U,V>这条边
for (int i=0;i<G[U].size();++i) if (G[U][i]==V) G[U][i]=0;
for (int i=0;i<G[V].size();++i) if (G[V][i]==U) G[V][i]=0;
dfs(GetCentre(U,n));//跑dfz
ret/=2ll;
int u=t;
while (true){
u=fa[u];
Circle.push_back(u);
if (u==t) break;
}
for (int i=0;i<Circle.size();++i) Mark[Circle[i]]=true;
//找到环上所有点,放在circle
//顺序:fa[t] ... t
for (int i=0;i<Circle.size();++i){
u=Circle[i];
//u到t的距离,第一个是逆时针,第二个是顺时针
QuerySubtree(u,0,Circle.size()-i-1);
AddSubtree(u,0,i+1);
}
printf("%lld\n",ret);
}
int main(){
n=read(),m=read(),k=read();
for (int i=1;i<=m;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
Max[0]=0x7fffffff;
if (m==n-1) SolveTree();
else SolveJHTree();
}

 评论