Codeforces 348E 树的中心点的性质 / 树形DP / 点分治

港控/mmm° 2021-12-12 02:04 244阅读 0赞

题意及思路：[http://ydc.blog.uoj.ac/blog/12][http_ydc.blog.uoj.ac_blog_12]

在求出树的直径的中心后，以它为根，对于除根以外的所有子树，求出子树中的最大深度，以及多个点的最大深度的lca，因为每个点的最长路径一定经过根，所以找到最大深度的子树，然后在这个点和最大深度的lca上树上差分一下就好了。注意，此处的中心是sum / 2处的那个点(sum是直径的长度）

代码：

#include <bits/stdc++.h>
    #define pii pair<int, int>
    using namespace std;
    const int maxn = 100010;
    int f[maxn];
    int d[maxn];
    vector<pii> G[maxn];
    int mx[maxn], mx_pos[maxn], dye[maxn], sum[maxn];
    int v[maxn];
    int ans, ans_cnt, root, pos, n, m;
    void add(int x, int y, int z) {
    	G[x].push_back(make_pair(y, z));
    	G[y].push_back(make_pair(x, z));
    }
    bool dfs(int x, int fa, int now) {
    	int flag = (v[x] == 1);
    	d[x] = now;
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		int tmp = dfs(y.first, x, now + y.second);
    		flag |= tmp;
    		f[y.first] = x;
    	}
    	if(flag && d[x] > ans) {
    		ans = d[x];
    		pos = x;
    	}
    	return flag;
    }
    void get_root() {
    	dfs(1, -1, 0);
    	memset(d, 0, sizeof(d));
    	ans = 0;
    	root = pos;
    	dfs(root, -1, 0);
    	int Sum = d[pos], tmp = pos;
    	while(d[tmp] > d[pos] / 2) {
    		tmp = f[tmp];
    	}
    	root = tmp;
    }
    void update(int pos, int ch, int val) {
    	if(mx[pos] < mx[ch] + val) {
    		mx[pos] = mx[ch] + val;
    		mx_pos[pos] = mx_pos[ch];
    	} else if(mx[pos] == mx[ch] + val) {
    		mx_pos[pos] = pos;
    	}
    }
    bool dfs1(int x, int fa, int color) {
    	dye[x] = color;
    	int flag = (v[x] == 1);
    	if(flag == 1) mx_pos[x] = x;
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		int tmp;
    		tmp = dfs1(y.first, x, color);
    		f[y.first] = x;
    		if(tmp) {
    			update(x, y.first, y.second);
    		}
    		flag |= tmp;
    	}
    	return flag;
    }
    void dfs2(int x, int fa) {
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		dfs2(y.first, x);
    		sum[x] += sum[y.first];
    	}
    	if(sum[x] > ans && v[x] == 0) {
    		ans = sum[x];
    		ans_cnt = 1;
    	} else if(sum[x] == ans && v[x] == 0) {
    		ans_cnt++;
    	}
    }
    vector<pii> res;
    map<int, int> mp;
    set<int> s;
    int tot;
    void solve() {
    	for (auto y : G[root]) {
    		int tmp = dfs1(y.first, root, ++tot);
    		if(tmp) {
    			res.push_back(make_pair(mx[y.first] + y.second, mx_pos[y.first]));
    		}
    	}
    	if(v[root] == 1) {
    		res.push_back(make_pair(0, root));
    	}
    	sort(res.begin(), res.end());
    	s.insert(dye[res[res.size() - 1].second]);
    	for (int i = res.size() - 1; i >= 1; i--) {
    		if(res[i].first == res[i - 1].first) {
    			s.insert(dye[res[i].second]);
    			s.insert(dye[res[i - 1].second]);
    		} else {
    			break;
    		}
    	}
    	for (int i = 0; i < res.size(); i++) {
    		mp[res[i].first]++;
    	}
    	for (int i = 1; i <= n; i++) {
    		if(v[i] == 1) {
    			if(s.count(dye[i]) && s.size() > 1) {
    				if(s.size() > 2) {
    					sum[i]++;
    				} else {
    					for (int j = res.size() - 1; j >= 0; j--) {
    						if(dye[i] != dye[res[j].second]) {
    							sum[i]++;
    							sum[res[j].second]++;
    							sum[root]--;
    							break;
    						}
    					}
    				}
    			} else {
    				if(s.size() > 1) {
    					sum[i]++;
    					continue;
    				}
    				if(dye[i] != dye[res[res.size() - 1].second]) {
    					sum[i]++;
    					sum[res[res.size() - 1].second]++;
    					sum[root]--;
    				}
    				else {
    					sum[i]++;
    					if(mp[res[res.size() - 2].first] == 1) {
    						sum[res[res.size() - 2].second]++;
    						sum[root]--;
    					}
    				}
    			}
    		}
    	}
    	ans = ans_cnt = 0;
    	dfs2(root, -1);
    }
    
    int main() {
    	int x, y, z;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= m ;i++) {
    		scanf("%d", &x);
    		v[x] = 1;
    	}
    	for (int i = 1; i < n; i++) {
    		scanf("%d%d%d", &x, &y, &z);
    		add(x, y, z);
    	}
    	get_root();
    	solve();
    	printf("%d %d\n", ans, ans_cnt);
    }

树形DP做法：我们不用树的直径中心的性质，可以通过树形DP求出最长链。怎么DP呢？首先对于每个点，我们维护在这颗子树中的所有点中，到这个点的最远的和次远的距离，以及这些点的LCA, 个数这些信息。之后，我们再DP一遍。到一个点的最路径，只有两种情况，一种是在子树内，一种是在子树外。对于在子树外的情况，我们可以通过到这个点的父亲节点的最长路径和自己的最长路径/次长路径，来确定到这个点的最长路径，然后去更新子树。剩下的操作和直径中心的操作一样了。

马上期末考试了，太忙了，代码先咕了，有时间再补QAQ

点分治做法继续留坑QAQ

转载于:https://www.cnblogs.com/pkgunboat/p/11000188.html

[http_ydc.blog.uoj.ac_blog_12]: http://ydc.blog.uoj.ac/blog/12