# BZOJ 3648. 寢室管理

### Brief description:

（(u -> v) 與 (v -> u) 算一組。。）

### Analysis:

```

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9, M = N*2;

namespace BIT{
const int N = ::N+::N+1;
int C[N], n;
void Add(int x, int d = 1){
x += ::N;
for (;x<N;x+=low_bit(x)) C[x] += d;
}
int Sum(int x){
x += ::N;
int res = 0; for (;x;x^=low_bit(x)) res += C[x];
return res;
}
int Rsum(int x){
int t = Sum(::N); t -= x + ::N > 0 ? Sum(x) : 0;
return t;
}
} //using namespace BIT;

int hd[N], prd[M], suc[M], to[M];
int m;

to[m] = b, suc[prd[hd[a]] = m] = hd[a], hd[a] = m++;
}

void add_edgee(int a, int b) {
}

#define aa to[i^1]
#define bb to[i]
#define v bb

inline void del(int i){
if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0;
else prd[suc[i]] = prd[i], suc[prd[i]] = suc[i];
}

inline void rsm(int i){
if (suc[i] == hd[aa]) hd[aa] = i;
prd[suc[i]] = suc[prd[i]] = i;
}

inline void dell(int i){
del(i), del(i^1);
}

inline void rsmm(int i){
rsm(i), rsm(i^1);
}

int n, k; int sz[N], dep[N]; LL ans; VI L;

void Scann(int u, int p) {
L.PB(dep[u]); REP_G(i, u) if (v != p){
dep[v] = dep[u] + 1;
Scann(v, u);
}
}

void Scan(int u){
CLR(L); dep[u] = 1; L.PB(dep[u]);
REP_G(i, u){
dep[v] = dep[u] + 1;
Scann(v, u);
}
}

namespace TDC{

int nn, cc, c;

void dfsc(int u, int p = 0){
int ss = 0; sz[u] = 1; REP_G(i, u) if (v != p){
dfsc(v, u), sz[u] += sz[v];
checkMax(ss, sz[v]);
}
checkMax(ss, nn - sz[u]);
if (ss <= cc) cc = ss, c = u;
}

void dfs0(int u, int p = -1){
sz[u] = 1; REP_G(i, u) if (v != p){
dep[v] = dep[u] + 1;
dfs0(v, u);
sz[u] += sz[v];
}
}

void dfs1(int u, int p){
L.PB(dep[u]);
REP_G(i, u) if (v != p){
dfs1(v, u);
}
}

void dfs2(int u, int p = -1){
REP_G(i, u) if (v != p){
dfs2(v, u);
}
}

void gao(int u = 1){

cc = INF, dfsc(u), u = c;

REP_G(i, u){
CLR(L); dfs1(v, u);
ECH(it, L) ans += BIT::Rsum(k-*it);
}

dfs2(u);

REP_G(i, u){
nn = sz[v], dell(i), gao(v), rsmm(i);
}
}
}

VI Circle; PII sta[N]; int pos[N], top = 0;

void dfs(int u = 1, int p = -1){ // Find_Circle
sta[pos[u]=++top].fi = u;
REP_G(i, u) if (i != (p^1)){
sta[top].se = i;
if (!pos[v]) dfs(v, i);
else {
FOR_1(ii, pos[v], top) {
Circle.PB(sta[ii].fi);
dell(sta[ii].se);
}
}
}
--top;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

m = 2; int m; RD(n, m, k); DO(m){
int a, b; RD(a, b);
}

if (m == n-1) TDC::gao();
else {

dfs(); ECH(c, Circle) TDC::gao(*c);

int d = 0;

ECH(c, Circle){
Scan(*c);
++d;
}

ECH(c, Circle){
Scan(*c);
ECH(it, L) ans += BIT::Rsum(k-d-*it);
++d;
}

ECH(c, Circle){
Scan(*c);