题意及思路: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

最新文章

  1. LeetCode Find All Numbers Disappeared in an Array
  2. 16.10.18学到的Java知识
  3. 2034-人见人爱A-B(c++实现)
  4. AFNetworking请求设置请求头
  5. 谈谈 Mifare Classic 破解
  6. HDU 3085 Nightmare Ⅱ (双向BFS)
  7. Springmvc+uploadify实现文件带进度条批量上传
  8. WPF弹性模拟动画
  9. “AIR SDK 0.0: AIR SDK location “...\devsdks\AIRSDK\Win” does not exist.”问题解决~
  10. DD应用实例
  11. 排序算法总结及Java实现
  12. 很全面的Android面试题
  13. Springboot文件上传与下载
  14. Linux安装网易云音乐
  15. sysbench的框架实现介绍
  16. PostgreSQL注入基础
  17. QT+VS2013 * 获取网络时间
  18. leetcode(js)算法605之种花问题
  19. 【读书笔记】iOS-“一心多用”利用多线程提升性能
  20. Linux分区设置

热门文章

  1. spring静态资源配置
  2. js 模板引擎 -Art Template
  3. Codeforces 1203F (贪心, DP)
  4. java改动后运行无变化
  5. Day One-Python基础
  6. 云数据库POLARDB产品解读之二:如何做到高性价比
  7. AcWing 226. 233矩阵 (矩阵快速幂+线性递推)打卡
  8. python random模块随机取list中的某个值
  9. hbase shell插入根据条件查询数据
  10. hive内部表&amp;外部表介绍