bzoj2282树形dp

Posted on   |   In

题解

首先路径的选择应该是直径的某一段区间…证明略(虽然我也是直观感受的)

然后我们考虑对直径上区间的选择 对于区间[l,r]的价值为$max(dis(直径左端点,l),max(dis(直径右端点,r),子区间上的价值))$

当$l$保持不变,$r$增加时,区间价值单调不增加,所以我们应该对于每个左端点$l$,找到最大r满足条件 然后统计

然后对于子区间价值的维护 我们可以找到每个点到离其最近直径上点距离的最大值更新并维护直径上点的价值

然后因为我单调队列 写挂了 就直接用线段树查询区间最大值即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
const int inf=1e9+10;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
 
 
int n;
int st[MAXN],tot,p[MAXN],dis[MAXN],s;
bool vis[MAXN];
queue<int>que;
int bfs(int x){
    inc(i,1,n)dis[i]=vis[i]=0;
    vis[x]=1;que.push(x);
    while(!que.empty()){
    int y=que.front();que.pop();
    link(y)if(!vis[j->t])vis[j->t]=1,dis[j->t]=dis[y]+j->v,que.push(j->t);
    }
    int pos=x;
    inc(i,1,n)if(dis[pos]<dis[i])pos=i;
    return pos;
}
 
int sum[MAXN],fa[MAXN],ans[MAXN],key[MAXN];
void dfs(int x,int pre){
    fa[x]=pre;
    link(x)if(j->t!=pre)sum[j->t]=sum[x]+j->v,key[j->t]=j->v,dfs(j->t,x);
}
 
void _dfs(int x,int y){
    int k;
    if(vis[x])k=x;else k=y;
    p[x]=k;
    link(x)if(j->t!=fa[x])_dfs(j->t,k);
}
 
int maxx[MAXN<<2],R[MAXN];
void built(int x,int l,int r){
    if(l==r){maxx[x]=ans[st[l]];return ;}
    int mid=(l+r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
    maxx[x]=max(maxx[x<<1],maxx[x<<1|1]);
}
 
int Maxx;
void query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){Maxx=max(Maxx,maxx[x]);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(x<<1,l,mid,ql,qr);
    if(qr>mid)query(x<<1|1,mid+1,r,ql,qr);
}
 
int main(){
    n=read();s=read();
    int x,y,z;
    inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    x=bfs(1);y=bfs(x);
    dfs(x,0);tot=0;
    inc(i,1,n)vis[i]=0;
    int k1=y;
    while(y)st[++tot]=y,vis[y]=1,y=fa[y];
    y=k1;
    _dfs(x,x);
    inc(i,1,n)ans[p[i]]=max(ans[p[i]],sum[i]-sum[p[i]]);
    built(1,1,tot);
    inc(i,1,tot)R[i]=R[i-1]+key[st[i]];
    int ans2=inf;
   // cout<<x<<" "<<y<<endl;
    inc(i,1,tot){
    int l=i;int r=tot;int ans1=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(R[mid]-R[i-1]<=s)ans1=mid,l=mid+1;
        else r=mid-1;
    }
    if(!ans1)ans1=i;else ans1=min(tot,ans1+1);
//  cout<<i<<"::: "<<ans1<<endl;
    Maxx=0;query(1,1,tot,i,ans1);
    ans2=min(ans2,max(Maxx,max(sum[y]-sum[st[i]],sum[st[ans1]]-sum[x])));
    }
    printf("%d\n",ans2);
    return 0; 
}

题目描述

某个国家有$n$个城市，这$n$个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为$z_i(z_i<=1000)$。

这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。

现在这个国家的经费足以在一条边长度和不超过$s$的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

Input

输入包含$n$行：
第$1$行，两个正整数$n$和$s$，中间用一个空格隔开。其中$n$为城市的个数,$s$为路径长度的上界。设结点编号以此为$1，2，……，n$。
从第$2$行到第$n$行，每行给出$3$个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，$“2 4 7”$表示连接结点$2$与$4$的边的长度为$7$。

Output

输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。