bzoj3648(点分治+树状数组)

Posted on   |   In

题解

分为两部分

对于树形结构 直接点分 然后排序/树状数组统计贡献

对于基环树结构 我们先把环取出来 以环上的点为根做点分治 统计每个子树内的贡献 然后考虑环上点的相互影响 对于每个子树维护每种深度的个数 然后我们可以考虑到每个点作用的是一段连续区间 可以采用树状数组来维护答案 时间复杂度是$O(nlogn)$ 至于环上点的维护 就是变环为链 然后维护即可

时间复杂度 $O(nlog^2n)$

代码实现

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
const int inf=1e9;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
 
int n,m,k;
int st[MAXN],tot,num[MAXN];
bool vis[MAXN];
vector<int>vec;
ll ans;
int f[MAXN],fa[MAXN];
int find1(int x){
    if(x==f[x])return x;
    return f[x]=find1(f[x]);
}
 
 
int rt,key,maxx[MAXN],sz[MAXN],base;
 
void get_root(int x,int pre){
    sz[x]=1;maxx[x]=0;
    link(x){
    if(vis[j->t]||j->t==pre)continue;
    get_root(j->t,x);
    sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
    }
    maxx[x]=max(maxx[x],base-sz[x]);
    if(key>maxx[x])key=maxx[x],rt=x;
}
int dis[MAXN];
int get_id(int x){return x&(-x);}
int sum[MAXN];
void update(int x,int y){
    for(int i=x;i<=n;i+=get_id(i))sum[i]+=y;
}
void clear(int x){
    for(int i=x;i<=n;i+=get_id(i))sum[i]=0;
}
int Sum(int x){
    int ans1=0;
    for(int i=x;i>0;i-=get_id(i))ans1+=sum[i];
    return ans1;
}
 
int St[MAXN],tot1;
void _dfs(int x,int pre){
    if(dis[x]<=k)ans+=Sum(n)-Sum(k-dis[x]);else ans+=Sum(n);
    st[++tot]=x;St[++tot1]=x;
    link(x){
    if(vis[j->t]||j->t==pre)continue;
    dis[j->t]=dis[x]+1;
    _dfs(j->t,x);
    }
}
 
void solve(int x){
    vis[x]=1;tot1=0;update(1,1);
    link(x){
    if(vis[j->t])continue;
    tot=0;dis[j->t]=2;_dfs(j->t,x);
    inc(i,1,tot)update(dis[st[i]],1);
    }
    inc(i,1,tot1)clear(dis[St[i]]);
    clear(1);
    link(x){
    if(vis[j->t])continue;
    key=inf;base=sz[j->t];get_root(j->t,0);
    solve(rt);
    }
}
 
int dep[MAXN];
int qko[MAXN];
void update1(int x,int y){
    for(int i=x;i<=3*n;i+=get_id(i))qko[i]+=y;
}
int Sum1(int x){
    int ans1=0;
    for(int i=x;i>0;i-=get_id(i))ans1+=qko[i];
    return ans1;
}
 
int Maxx;
void __dfs(int x,int pre,int deep){
    dep[deep]++;Maxx=max(Maxx,deep);
    link(x){
    if(vis[j->t]||j->t==pre)continue;
    __dfs(j->t,x,deep+1);
    }
}
 
typedef struct node{
    int x,y;
}node;
node que[MAXN];
 
int Num[MAXN];
vector<int>Vec[MAXN];
void dfs(int x,int pre){
    fa[x]=pre;
    for(int i=0;i<Vec[x].size();i++){
    if(Vec[x][i]==pre)continue;
    dfs(Vec[x][i],x);
    }
}
 
 
int main(){
    n=read();m=read();k=read();
    int x,y;
    inc(i,1,n)f[i]=i;
    inc(i,1,m)x=read(),y=read(),add(x,y),add(y,x),que[i]=(node){x,y};
    x=0;y=0;
    inc(i,1,m){
    int t1=find1(que[i].x);int t2=find1(que[i].y);
    if(t1==t2){x=que[i].x;y=que[i].y;continue;}
    Vec[que[i].x].pb(que[i].y);
    Vec[que[i].y].pb(que[i].x);
    f[t1]=t2;
    }
    if(x){
    dfs(1,0);
    int root;
    int x1=x;int y1=y;
    while(x)Num[x]++,x=fa[x];
    while(y){
        if(Num[y]){root=y;break;}
        y=fa[y];
    }
    x=x1;y=y1;
    while(x!=root)vec.pb(x),x=fa[x];
    vec.pb(root);int t=vec.size();
    while(y!=root)vec.pb(y),y=fa[y];
    reverse(vec.begin()+t,vec.end());
    }
    inc(i,1,n)vis[i]=0;
    int t=vec.size();
    ans=0;
    if(t){
     inc(i,0,t-1)vis[vec[i]]=1;
     inc(i,0,t-1){
         vis[vec[i]]=0;
         base=num[vec[i]];key=inf;get_root(vec[i],0);
         solve(rt);
         vis[vec[i]]=1;
     }
    inc(i,1,n)vis[i]=0;
    inc(i,0,t-1)vis[vec[i]]=1;
    vis[vec[0]]=0;Maxx=0;__dfs(vec[0],0,1);vis[vec[0]]=1;
    inc(i,0,t-2)vec.pb(vec[i]);
    inc(i,1,Maxx){
        int l=max(1,k+1-i);int r=1+t;
        update1(l,dep[i]);
        dep[i]=0;
    }
    for(int i=1;i<vec.size();i++){
        vis[vec[i]]=0;Maxx=0;__dfs(vec[i],0,1);vis[vec[i]]=1;
        inc(j,1,Maxx){
        int l=max(i+1,k+i+1-j-t);
        if(i>=t)update1(l,-dep[j]);
        }
        inc(j,1,Maxx){
        int pos=i+j;
        ans+=1ll*Sum1(pos)*dep[j];
        }
        inc(j,1,Maxx){
        int l=max(i+1,k+i+1-j);
        if(i<t)update1(l,dep[j]);
        dep[j]=0;
        }
    }
    printf("%lld\n",ans);
    }
    else{
    base=n;key=inf;get_root(1,0);
    solve(rt);
    printf("%lld\n",ans);
    }
    return 0;
}

题目描述

T64有一个好朋友，叫T128。T128是寄宿生，并且最近被老师叫过去当宿管了。宿管可不是一件很好做的工作，碰巧T128有一个工作上的问题想请T64帮忙解决。T128的寝室条件不是很好，所以没有很多钱来装修。礼间寝室仅由$n-1$条双向道路连接，而且任意两间寝室之间都可以互达。最近，T128被要求对一条路径上的所有寝室进行管理，这条路径不会重复经过某个点或某条边。但他不记得是哪条路径了。他只记得这条路径上有不少于$k$个寝室。于是，他想请T64帮忙数一下，有多少条这样的路径满足条件。嗯…还有一个问题。由于最近有一些熊孩子不准晚上讲话很不爽，他们决定修筑一条“情报通道”，如果通道建成，寝室就变成了一个$N$个点$N$条边的无向图。并且，经过“情报通道”的路径也是合法的。T128心想：通道建成之前，T64还有一个高效的算法帮我数路径条数，但是通道建成之后，他还有办法吗？对，T64手忙脚乱，根本数不清有多少条路径。于是他找到了你。

Input

第一行为三个正整数$N$，$M$，$K（2 ≤ K ≤ N）$，代表有$n$间寝室，$m$条边连接它们$n-1 ≤ m ≤ N$；

$m= n-1$意味着“情报遁道”未被修好；$m=n$意味着“情报通道”已被修好），以及题目描述中的$K$。

接下来$m$行，每行两个正整数$z$，$y$，代表第$x$间寝室与第$y$间寝室之间有一条双向边。

Output

仅包含一个整数，代表经过至少$K$间寝室的路径条数。