[데이터 구조 스캐닝 라인] 공간 단순 도

제목
나무 한 그루 를 주 십시오. 그 중 일 부 는 합 법 적 이지 않 습 니 다. 모두 몇 개의 경로 중 합 법 적 이지 않 은 점 이 없 기 를 바 랍 니 다.
사고의 방향
모든 경로 - 비합법적 인 경로 로 답 을 얻 는 것 을 고려 하 다.각 점 대 (x, y) 에 대해 dfn [x] 가 만약 에 x 가 y 의 조상 이 라면 y 의 서브 트 리 는 x ~ y 라 는 체인 을 제외 한 다른 노드 는 모두 합 법 적 이지 않다. 만약 에 x 가 y 의 조상 이 아니라면 x 의 서브 트 리 에서 y 의 서브 트 리 까지 의 점 은 모두 합 법 적 이지 않다. 중복 되 는 비합법적 인 점 이 계산 되 기 때문에 우 리 는 그것들 을 좌표계 에 던 져 면적 을 구 할 것 이다.
코드

#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include 
#include 
#include 
#include 

int dfn[3000001], d[3000001], size[3000001], f[3000001][21];
int ver[6000001], next[6000001], head[6000001];
int n, k, tot, cnt;
long long ans;

inline long long read()
{
	long long f = 0, d = 1;
	char c; 
	while (c = getchar(), !isdigit(c)) if (c == '-') d = -1;
	f = (f << 3) + (f << 1) + c - 48;
	while (c = getchar(), isdigit(c)) f = (f << 3) + (f << 1) + c - 48;
	return d * f;
}

struct treenode {
	int l, r, len, sum;
}tree[12000001];

struct node {
	int l, r, h, mark;
}line[6000001];

bool operator < (node x, node y) {
	return x.h < y.h;
}

void build(int p, int l, int r) {
	tree[p].l = l;
	tree[p].r = r;
	tree[p].len = tree[p].sum = 0;
	if (l == r) return;
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void spread(int p) {
	int l = tree[p].l, r = tree[p].r;
	if (tree[p].sum) tree[p].len = r - l + 1;
	else tree[p].len = tree[p << 1].len + tree[p << 1 | 1].len;
}

void change(int p, int L, int R, int val) {
	int l = tree[p].l, r = tree[p].r;
	if (r < L || l > R) return;
	if (l >= L && r <= R) {
		tree[p].sum += val;
		spread(p);
		return;
	}
	change(p << 1, L, R, val);
	change(p << 1 | 1, L, R, val);
	spread(p);
}

void add(int u, int v) {
	ver[++tot] = v;
	next[tot] = head[u];
	head[u] = tot;
}

void dfs(int p) {
	size[p] = 1;
	dfn[p] = ++dfn[0];
    for (int i = head[p]; i; i = next[i]) {
    	if (d[ver[i]]) continue;
    	d[ver[i]] = d[p] + 1;
    	f[ver[i]][0] = p;
    	for (int j = 1; j <= 20; j++)
    		f[ver[i]][j] = f[f[ver[i]][j - 1]][j - 1];
    	dfs(ver[i]);
    	size[p] += size[ver[i]];
	}
}

int LCA(int x, int y) {
    for (int i = 20; i >= 0; i--)
		if (d[f[y][i]] > d[x]) y = f[y][i];
	return y;
}

void addl(int x1, int x2, int y1, int y2) {
	if (x1 > x2) std::swap(x1, x2);
	if (y1 > y2) std::swap(y1, y2);
	line[++cnt] = (node){x1, x2, y1, 1};
	line[++cnt] = (node){x1, x2, y2 + 1, -1};
}

void doit(int x, int y) {
	if (dfn[x] > dfn[y]) std::swap(x, y);
	if (dfn[y] <= dfn[x] + size[x] - 1 && dfn[y] > dfn[x]) {
		int son = LCA(x, y);
		if (dfn[son] > 1) addl(1, dfn[son] - 1, dfn[y], dfn[y] + size[y] - 1);
		if (dfn[son] + size[son] - 1 < n) addl(dfn[y], dfn[y] + size[y] - 1, dfn[son] + size[son], n);
	} else addl(dfn[x], dfn[x] + size[x] - 1, dfn[y], dfn[y] + size[y] - 1);
}

int main() {
	int size = 256 << 20;
    char *p = (char*)malloc(size) + size;
    __asm__("movl %0, %%esp
" :: "r"(p));
	n = read();
	k = read();
	for (int i = 1, x, y; i < n; i++) {
		x = read();
		y = read();
		add(x, y);
		add(y, x);
	}
	d[1] = 1;
	dfs(1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k && i + j <= n; j++)
			doit(i, i + j);
	build(1, 1, n);
	std::sort(line + 1, line + 1 + cnt);
	for (int i = 1; i < cnt; i++) {
		change(1, line[i].l, line[i].r, line[i].mark);
		ans += (long long)tree[1].len * (line[i + 1].h - line[i].h);
	}
	printf("%lld", (long long)n * (n - 1) / 2 - ans + n);
}