icontofig | 发布于 2019-07-04 14:41:30 | 阅读量 207 | 线段树 DP BFS

## 题解

1.非此直径上的点到当前选定的核的距离的最大值。

2.直径的两个端点到当前选定的核的距离的最大值。

## 代码

```#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
int get_num() {
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\r' || c == '\n');
if (c == '-')
flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 500005;
struct edge {
int to, next, v;
}e[maxn << 1];
int h[maxn], dis[maxn], pre[maxn], fa[maxn], mdis[maxn], qz[maxn];
bool vis[maxn];
int ax[maxn];
int n, k, st, en, cnt = 0;
int mx = 0, pos, now = 0;
struct seg {
int l, r, val;
}tr[maxn<<2];
void push_up(int now) {
tr[now].val = max(tr[now << 1 | 1].val, tr[now << 1].val);
return;
}
void build(int now, int l, int r) {
tr[now].l = l;
tr[now].r = r;
if (l == r) {
tr[now].val = mdis[ax[l]];
return;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
push_up(now);
return;
}
int query(int now, int l, int r) {
if (tr[now].l >= l && tr[now].r <= r)
return tr[now].val;
int mid = (tr[now].l + tr[now].r) >> 1;
int ans = 0;
if (l <= mid)ans = max(ans, query(now << 1, l, r));
if (r > mid)ans = max(ans, query(now << 1 | 1, l, r));
return ans;
}
void init() {
memset(dis, 0, sizeof(dis));
memset(e, 0, sizeof(e));
memset(h, -1, sizeof(h));
memset(ax, 0, sizeof(ax));
memset(vis, 0, sizeof(vis));
return;
}
void BFS(int s, int b) {
dis[s] = 0;
fa[s] = s;
queue<int>q;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = h[x]; i != -1; i = e[i].next) {
if (dis[e[i].to] != 0 || e[i].to == s)continue;
dis[e[i].to] = dis[x] + e[i].v;
if (b == 1) {
pre[e[i].to] = e[i].v;
fa[e[i].to] = x;
}
if (mx <= dis[e[i].to]) {
pos = e[i].to;
mx = dis[e[i].to];
}
q.push(e[i].to);
}
}
return;
}
void DFS(int s, int top) {
dis[top] = 0;
for (int i = h[s]; i != -1; i = e[i].next) {
if (vis[e[i].to])continue;
if (dis[e[i].to] != 0)continue;
dis[e[i].to] = dis[s] + e[i].v;
mdis[top] = max(mdis[top], dis[e[i].to]);
DFS(e[i].to, top);
}
return;
}
void add(int a, int b, int c) {
e[now].to = b; e[now].v = c;
e[now].next = h[a]; h[a] = now++;
return;
}
int p[maxn],op = 0;
int main() {
n = get_num();
k = get_num();
int a, b, c;
init();
for (int i = 1; i < n; ++i) {
a = get_num();
b = get_num();
c = get_num();
}
BFS(1, 0);
st = pos;
mx = 0;
int ansp = INF;
for(int i = 1;i <= n;++i)dis[i] = 0;
BFS(pos, 1);
for(int i = 1;i <= n;++i){
if(dis[i] == mx)p[++op] = i;
}
for(int g = 1;g <= op;++g){
en = p[g];
int x = en;
for(int i = 1;i <= n;++i){
mdis[i] = 0;
ax[i] = 0;
vis[i] = false;
qz[i] = 0;
}
while (fa[x] != x) {
ax[++cnt] = x;
vis[x] = true;
x = fa[x];
}
ax[++cnt] = st;
vis[st] = true;
qz[1] = 0;
for(int i = 1;i <= n;++i)dis[i] = 0;
for (int i = 1; i <= cnt; ++i) {
DFS(ax[i], ax[i]);
if (i >= 2)qz[i] = qz[i - 1] + pre[ax[i-1]];
}
int i = 1, j = 1, ansx = 0;
build(1, 1, cnt);
while (j < cnt) {
while (qz[j+1] - qz[i]  <= k){
j++;
if(j == cnt)break;
}
ansx = max(query(1,i,j),qz[i] - qz[1]);
ansx = max(ansx,qz[cnt] - qz[j]);
ansp = min(ansp, ansx);
++i;
if(i > j)j = i;
}
}
printf("%d\n", ansp);
return 0;
}```

207 人读过

0 条评论