3648: 寝室管理
Time Limit: 40 Sec Memory Limit: 512 MB
Submit: 366 Solved: 152
[Submit][Status][Discuss]
Description
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间寝室的路径条数。
Sample Input
5 5 2
1 3
2 4
3 5
4 1
5 2
1 3
2 4
3 5
4 1
5 2
Sample Output
20
HINT
N≤100000
K≤N
M=N
如果是一棵树，就是普通的点分治，对于u为根，统计每棵子树的深度并用树状数组统计相加大于等于K的答案
如果加上一个环，我们用tarjan算法找出环，拆掉其中一条边，就可以跑一遍点分治算出不经过该边的方案
再来就考虑经过该边，朝该边的一个方向逐个访问环上各点
对于点u，先统计其外向树的深度，再与u之前的点的外向树维护的树状数组，计算跨过拆掉的边所形成的答案
如图：
每到一个外向树，先统计顺时针走到断边后之前有多少点可以满足相加>=K，统计完后再将自己逆时针走到断边的长度记入树状数组
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
#define lbt(x) (x & -x)
using namespace std;
const int maxn = 100005,maxm = 200005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int N,M,K,h[maxn],ne = 0;
int F[maxn],rt,Sum,Siz[maxn],vis[maxn];
int d[maxn],t[maxn],n,A[maxn];
int cir[maxn],ciri = 0,dfn[maxn],st[maxn],top = 0,cnt = 0,sta[maxn],tp = 0;
LL ans = 0;
struct EDGE{int to,nxt,v;}ed[maxm];
inline void build(int u,int v){
ed[ne] = (EDGE){v,h[u],1}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v],1}; h[v] = ne++;
}
inline void add(int u,int v){while (u <= N) A[u] += v,u += lbt(u);}
inline int query(int u){int ans = 0; while (u) ans += A[u],u -= lbt(u); return ans;}
inline int sum(int l,int r){return query(r) - query(l - 1);}
void getRT(int u,int f){
int to; F[u] = 0; Siz[u] = 1;
Redge(u) if (ed[k].v && (to = ed[k].to) != f && !vis[to]){
getRT(to,u); F[u] = max(F[u],Siz[to]); Siz[u] += Siz[to];
}
F[u] = max(F[u],Sum - Siz[u]);
if (F[u] < F[rt]) rt = u;
}
void dfs(int u,int f){
t[++n] = u; int to;
Redge(u) if (ed[k].v && !vis[to = ed[k].to] && to != f)
d[to] = d[u] + 1,dfs(to,u);
}
void solve(int u){
vis[u] = true; int to;
add(1,1);
Redge(u) if (ed[k].v && !vis[to = ed[k].to]){
n = 0; d[to] = 2; dfs(to,u);
REP(i,n) ans += sum(max(1,K - d[t[i]] + 1),N);
REP(i,n) add(d[t[i]],1);
}
Redge(u) if (ed[k].v && !vis[to = ed[k].to]){
n = 0; d[to] = 2; dfs(to,u);
REP(i,n) add(d[t[i]],-1);
}
add(1,-1);
Redge(u) if (ed[k].v && !vis[to = ed[k].to]){
Sum = Siz[to]; F[rt = 0] = INF; getRT(to,u);
solve(rt);
}
}
void dfs1(int u,int pre){
dfn[u] = ++cnt; st[++top] = sta[++tp] = u; int to;
Redge(u){
if (k == pre) continue;
if (!dfn[to = ed[k].to]) dfs1(to,k ^ 1);
else while (dfn[st[top]] > dfn[to]) top--;
}
if (st[top] == u){
if (ciri > 1) return;
ciri = 0; top--;
do { cir[++ciri] = sta[tp]; } while (sta[tp--] != u);
}
}
void solve1(){
F[rt = 0] = INF; Sum = N; getRT(1,0);
solve(rt);
cout<<ans<<endl;
}
void solve2(){
dfs1(1,-1);
Redge(cir[1]) if (ed[k].to == cir[ciri]) {ed[k].v = ed[k ^ 1].v = 0; break;}
F[rt = 0] = INF; Sum = N; getRT(1,0);
solve(rt);
memset(vis,false,sizeof(vis));
for (int i = 1; i <= ciri; i++){
int u = cir[i],len = ciri - i;
n = 0; vis[cir[i - 1]] = vis[cir[i + 1]] = true; d[u] = 1;
dfs(u,0);
vis[cir[i - 1]] = vis[cir[i + 1]] = false;
REP(j,n) ans += sum(max(1,K - d[t[j]] - len),N);
REP(j,n) add(d[t[j]] + i - 1,1);
}
cout<<ans<<endl;
}
int main(){
memset(h,-1,sizeof(h));
N = RD(); M = RD(); K = RD();
REP(i,M) build(RD(),RD());
if (M < N) solve1();
else solve2();
return 0;
}