POJ 3162 Walking Race
6717 단어 트리 dp
Time Limit: 10000MS
Memory Limit: 131072K
Total Submissions: 4139
Accepted: 1037
Case Time Limit: 3000MS
Description
flymouse’s sister wc is very capable at sports and her favorite event is walking race. Chasing after the championship in an important competition, she comes to a training center to attend a training course. The center has N check-points numbered 1 through N. Some pairs of check-points are directly connected by two-way paths. The check-points and the paths form exactly a tree-like structure. The course lasts N days. On the i-th day, wc picks check-point i as the starting point and chooses another check-point as the finishing point and walks along the only simple path between the two points for the day’s training. Her choice of finishing point will make it that the resulting path will be the longest among those of all possible choices.
After every day’s training, flymouse will do a physical examination from which data will obtained and analyzed to help wc’s future training be better instructed. In order to make the results reliable, flymouse is not using data all from N days for analysis. flymouse’s model for analysis requires data from a series of consecutive days during which the difference between the longest and the shortest distances wc walks cannot exceed a bound M. The longer the series is, the more accurate the results are. flymouse wants to know the number of days in such a longest series. Can you do the job for him?
Input
The input contains a single test case. The test case starts with a line containing the integers N (N ≤ 106) and M (M < 109). Then follow N − 1 lines, each containing two integers fi and di (i = 1, 2, …, N− 1), meaning the check-points i + 1 and fi are connected by a path of length di.
Output
Output one line with only the desired number of days in the longest series.
Sample Input
3 2
1 1
1 3
Sample Output
3
Hint
Explanation for the sample:
There are three check-points. Two paths of lengths 1 and 3 connect check-points 2 and 3 to check-point 1. The three paths along with wc walks are 1-3, 2-1-3 and 3-1-2. And their lengths are 3, 4 and 4. Therefore data from all three days can be used for analysis.
Source
POJ Monthly--2006.12.31, flymouse
제목: 나무 한 그루는 가장자리마다 가장자리가 있다.우선 각 노드가 가장 멀리 도착할 수 있는 거리를 구하고, 그 다음에 노드의 번호에 따라 이 거리를 정렬해야 한다.구간 최대치를 만족시키고 최소치를 빼면 m보다 크지 않은 연속 구간 최대가 얼마냐고 물었다.
우선 첫 번째 단계는 각 노드에서 가장 먼 거리를 구하는 것을 어렵지 않게 알 수 있다. 트리 dp, XJB로 쓰면 된다. 그러면 문제는 어떻게 맞는 구간을 찾느냐에 달려 있다. 처음에 여기가 끊겼는데 뒤에 보니 처음에는 l=r=1만 있었다. 그리고 매번 맞으면 r++, 그렇지 않으면 l++, r++를 물어보면 된다.이것도 n번 물어봐야 돼. 그러니까 복잡도는 충분해.동시에 구간 문의 조작만 했기 때문에 RMQ를 하려고 했는데 MLE가 되어 어색해서 라인 트리에 솔직하게 감사를 드렸다.
//******************************************************************************************
//AC
//Ninaye
//******************************************************************************************
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int maxn = 1e6+10;
int n;
LL value[maxn],m;
struct DP{
LL f_val,s_val_1,s_val_2;
int son1,son2;
}dp[maxn];
int head[maxn],_cnt;
struct Edge{
int to,next;
LL w;
}edge[maxn<<1];
inline void init(){
for(int i = 0; i <= n; i++){
head[i] = -1;
dp[i].son1 = dp[i].son2 = -1;
dp[i].f_val = dp[i].s_val_1 = dp[i].s_val_2 = 0;
value[i] = 0;
}
_cnt = 0;
}
inline void ADD(int u,int v,LL w){
edge[_cnt].to = v;
edge[_cnt].next = head[u];
edge[_cnt].w = w;
head[u] = _cnt++;
}
inline void dfs_1(int now,int fa){
for(int i = head[now]; ~i; i = edge[i].next){
int v = edge[i].to;
if(v != fa){
value[v] = edge[i].w;
dfs_1(v,now);
if(dp[now].son1 == -1){
dp[now].son1 = v;
dp[now].s_val_1 = dp[v].s_val_1+value[v];
}
else if(dp[now].son2 == -1){
dp[now].son2 = v;
dp[now].s_val_2 = dp[v].s_val_1+value[v];
if(dp[now].s_val_1 < dp[now].s_val_2){
swap(dp[now].s_val_1,dp[now].s_val_2);
swap(dp[now].son1,dp[now].son2);
}
}
else if(dp[now].s_val_2 < dp[v].s_val_1+value[v]){
dp[now].son2 = v;
dp[now].s_val_2 = dp[v].s_val_1+value[v];
if(dp[now].s_val_1 < dp[now].s_val_2){
swap(dp[now].s_val_1,dp[now].s_val_2);
swap(dp[now].son1,dp[now].son2);
}
}
}
}
}
inline void dfs_2(int now,int fa){
if(fa == 0)
dp[now].f_val = 0;
else if(now != dp[fa].son1)
dp[now].f_val = max(dp[fa].s_val_1,dp[fa].f_val)+value[now];
else
dp[now].f_val = max(dp[fa].s_val_2,dp[fa].f_val)+value[now];
for(int i = head[now]; ~i; i = edge[i].next){
int v = edge[i].to;
if(v != fa)
dfs_2(v,now);
}
}
struct Info{
LL Min,Max;
int l,r;
};
struct SGT{
Info tree[maxn<<2];
inline void push_up(int now){
tree[now].Min = min(tree[now<<1].Min,tree[now<<1|1].Min);
tree[now].Max = max(tree[now<<1].Max,tree[now<<1|1].Max);
}
inline void build(int now,int l,int r){
tree[now].l = l;
tree[now].r = r;
if(l == r){
tree[now].Min = tree[now].Max = value[l];
return;
}
int Mid = (l+r)>>1;
build(now<<1,l,Mid);
build(now<<1|1,Mid+1,r);
push_up(now);
}
inline LL que_Max(int now,int l,int r){
if(l <= tree[now].l && tree[now].r <= r){
return tree[now].Max;
}
LL ans = 0;
int Mid = (tree[now].l + tree[now].r)>>1;
if(l <= Mid)
ans = max(ans,que_Max(now<<1,l,r));
if(Mid < r)
ans = max(ans,que_Max(now<<1|1,l,r));
return ans;
}
inline LL que_Min(int now,int l,int r){
if(l <= tree[now].l && tree[now].r <= r){
return tree[now].Min;
}
LL ans = INF;
int Mid = (tree[now].l + tree[now].r)>>1;
if(l <= Mid)
ans = min(ans,que_Min(now<<1,l,r));
if(Mid < r)
ans = min(ans,que_Min(now<<1|1,l,r));
return ans;
}
inline LL que(int l,int r){
return que_Max(1,l,r)-que_Min(1,l,r);
}
}sgt;
int main(){
int v;
LL w;
while(~scanf("%d %lld",&n,&m)){
init();
for(int i = 1; i < n; i++){
scanf("%d %lld",&v,&w);
ADD(i+1,v,w);
ADD(v,i+1,w);
}
dfs_1(1,0);
dfs_2(1,0);
for(int i = 1; i <= n; i++)
value[i] = max(dp[i].f_val,dp[i].s_val_1);
sgt.build(1,1,n);
int l,r,ans;
ans = 0;
l = r = 1;
while(l <= r && r <= n){
if(sgt.que(l,r) <= m){
ans = r-l+1;
r++;
}
else{
l++,r++;
}
}
printf("%d
",ans);
}
return 0;
}
/*
input
11 2
1 1
2 2
2 3
4 1
5 2
1 1
7 2
8 3
9 1
9 2
output
3
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
codeforces 855C 트리 DP간략한 제목: 나무 한 그루를 주면 m가지 색깔이 있고, k가지 색깔은 특수 색깔이며, 나무에는 최대 x개의 특수 색깔 포인트가 있다.당신은 나무 전체를 염색하고 특수 색 노드의 다음 조건을 확보해야 합니다. 1.연...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.