[Luogu p4183] cow at large P (graph theory) (tree array)

Cow at Large P

Topic link ：luogu P4183

The main idea of the topic

Give you a tree , Then the leaf node can put guards .
Then there was a man in the tree , Then that person and the guard can move every moment , If a man meets a guard, he will be caught , If a person walks to the leaf node, he escapes .
Then ask you about the position on each tree , If that person was here at the beginning , At least how many guards are needed to catch him .

Ideas

First of all, it is not difficult to see a simple thing because it is a tree , So if we take that person's initial position as the root .
The guard will go up , The longer the time, the more roads that person will break .
So we only need to choose one guard in a subtree , Let's take a look at the position of the point at the top of the subtree .

Then you will find that if you can't keep it , That man goes this way , Let the top point be $x$, The nearest leaf node is $y$（ Because the guard must have put it here ）, At first, people were $z$, That's it $dis(x,z)⩾dis(x,y)$ and $dis(f{a}_x,z)<dis(x,y)$.
This critical point is not easy to deal with , Consider making it more common , Just look at the conditions that the formula on the left satisfies .

You will find that the satisfaction is the vertex and its subtree , Can you think of a way to make the whole subtree contribute only once .
Then there is the point edge relationship in graph theory , stay $n$ On the subtree of points , Yes ：
$\sum ^{n}d{u}_i=2n-1$
（ Because the point at the top of the subtree is connected with a father ）
$1=2n-\sum ^{n}d{u}_i=\sum ^n(2-d{u}_i)$

So the answer can be this ：
$an{s}_x=\sum _{i=1}^n[dis(x,i)⩾g_i](2-d{u}_i)$
Then this is a point-to-point problem, which can be divided and treated by points , Then use a tree array to store buckets .

Code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 7e4 + 100;
int n, sz[N], root, max_root, du[N], g[N], dis[N], ans[N];
vector <int> G[N];
bool in[N];

struct SZSJ {
    
	int f[N << 1], n;
	
	void clear(int m) {
    
		n = m; for (int i = 1; i <= n; i++) f[i] = 0;
	}
	
	void add(int x, int y) {
    
		for (; x <= n; x += x & (-x))
			f[x] += y;
	}
	
	int query(int x) {
    
		int re = 0;
		for (; x; x -= x & (-x))
			re += f[x];
		return re;
	}
}T;

void Init() {
    
	queue <int> q;
	for (int i = 1; i <= n; i++) if (du[i] == 1) q.push(i), in[i] = 1;
	while (!q.empty()) {
    
		int now = q.front(); q.pop();
		for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
			if (in[x]) continue;
			g[x] = g[now] + 1; in[x] = 1; q.push(x);
		}
	}
	memset(in, 0, sizeof(in));
	dis[0] = -1;
}

void dfs0(int now, int father) {
    
	sz[now] = 1; dis[now] = dis[father] + 1;
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (x == father || in[x]) continue;
		dfs0(x, now); sz[now] += sz[x];
	}
}

void get_root(int now, int father, int sum) {
    
	int maxn = sum - sz[now];
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (x == father || in[x]) continue;
		get_root(x, now, sum);
		maxn = max(maxn, sz[x]);
	}
	if (maxn < max_root) max_root = maxn, root = now;
}

int dadi;

void dfs1(int now, int father) {
    
	ans[now] += T.query(dis[now] + dadi);
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (x == father || in[x]) continue;
		dfs1(x, now);
	}
}

void dfs2(int now, int father) {
    
	T.add(g[now] - dis[now] + dadi, 2 - du[now]);// Add sz[now] Prevent negative sign  
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (x == father || in[x]) continue;
		dfs2(x, now);
	}
}

void clac(int now) {
    
	dadi = sz[now]; 
	T.clear(sz[now] * 2);
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (in[x]) continue;
		dfs1(x, now);
		dfs2(x, now);
	}
	T.clear(sz[now] * 2);
	T.add(g[now] + dadi, 2 - du[now]);
	for (int i = G[now].size() - 1; i >= 0; i--) {
     int x = G[now][i];
		if (in[x]) continue;
		dfs1(x, now);
		dfs2(x, now);
	}
	ans[now] += T.query(dadi);
}

void work(int now) {
    
	in[now] = 1;
	dfs0(now, 0);
	clac(now);
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (in[x]) continue;
		max_root = 2e9; get_root(x, now, sz[x]);
		work(root);
	}
}

int main() {
    
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y); G[y].push_back(x);
		du[x]++; du[y]++;
	}
	
	Init();
	
	dfs0(1, 0);
	max_root = 2e9; get_root(1, 0, n);
	work(root);
	
	for (int i = 1; i <= n; i++)
		if (du[i] != 1) printf("%d\n", ans[i]);
			else printf("1\n");
	
	return 0;
}