1.给你一棵边带权的树,求出树中每一个点到其它点的最大距离。
2.在一个整数序列中找一个最大的连续序列,使得该序列中最大数和最小数之差不超过 m 。
问题 1 可用树形 DP 解决。对树进行 DFS,DFS 过程中,对根 R,记录他的孩子结点到他是最大距离和次大距离以及相应的结点。然后用一次 BFS 更新。
问题 2 用两个指针 head, tail分别指向连续序列的首尾,如果区间 [head,tail] 满足条件,则 tail++,更新值最大最小值,不满足条件则 head++, 用线段树更新最大最小值。
注意图不能用 STL 的 vector 和 pair 保存,这样会 TLE。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int const N= 1000010, inf= 0x7fffffff;
int dp[N][2], pos[N][2], flag[N], que[N];
int n, m, cnt;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct Edge{
int adj, wt;
Edge* next;
}EG[N<<1];
Edge* mat[N];
struct TB{
int Min, Max;
}tb[N<<2];
inline void add( int u, int v, int d ){
++cnt;
EG[cnt].adj= v; EG[cnt].wt= d;
EG[cnt].next= mat[u]; mat[u]= EG+ cnt;
cnt++;
EG[cnt].adj= u; EG[cnt].wt= d;
EG[cnt].next= mat[v]; mat[v]= EG+ cnt;
}
int dfs( int u ){
dp[u][0]= 0; dp[u][1]= 0; flag[u]= 1;
for( Edge* p= mat[u]; p; p= p->next )
if( !flag[p->adj] ){
int v= p->adj, w= p->wt;
int tmp= w+ dfs( v );
if( tmp> dp[u][0] ){
dp[u][1]= dp[u][0]; pos[u][1]= pos[u][0];
dp[u][0]= tmp; pos[u][0]= v;
}
else if( tmp> dp[u][1] ){
dp[u][1]= tmp; pos[u][1]= v;
}
}
return dp[u][0];
}
void bfs( int rt ){
for( int i= 0; i<= n; ++i ) flag[i]= 0;
int head= 0, tail= 0; que[0]= rt; flag[rt]= 1;
while( head<= tail ){
int u= que[head++];
for( Edge* p= mat[u]; p; p= p->next )
if( !flag[p->adj] ){
int v= p->adj, w= p->wt;
flag[v]= 1; que[++tail]= v;
if( pos[u][0]== v ) w+= dp[u][1];
else w+= dp[u][0];
if( w> dp[v][0] ){
dp[v][1]= dp[v][0]; pos[v][1]= pos[v][0];
dp[v][0]= w; pos[v][0]= u;
}
else if( w> dp[v][1] ){
dp[v][1]= w; pos[v][1]= u;
}
}
}
}
void build( int L, int R, int rt ){
if( L== R ){
tb[rt].Max= tb[rt].Min= dp[L][0]; return; }
int mid= (L+ R)>> 1;
build( L, mid, rt<<1 );
build( mid+ 1, R, rt<<1|1 );
tb[rt].Max= max( tb[rt<<1].Max, tb[rt<<1|1].Max );
tb[rt].Min= min( tb[rt<<1].Min, tb[rt<<1|1].Min );
}
int ansMin, ansMax;
void query( int x, int y, int L, int R, int rt ){
if( L== x && y== R || L== R ){
ansMin= min( ansMin, tb[rt].Min );
ansMax= max( ansMax, tb[rt].Max );
return;
}
int mid= (L+ R)>>1;
if( y<= mid ) query( x, y, L, mid, rt<<1 );
else if( x> mid ) query( x, y, mid+ 1, R, rt<<1|1 );
else{
query( x, mid, L, mid, rt<<1 );
query( mid+ 1, y, mid+ 1, R, rt<<1|1 );
}
}
int main(){
scanf("%d%d",&n,&m ); cnt= -1;
for( int i= 0; i<= n; ++i ){
mat[i]= 0; flag[i]= 0;
}
for( int i= 2; i<= n; ++i ){
int x, y;
scanf("%d%d",&x,&y);
add( i, x, y );
}
dfs(1); bfs(1); build(1,n,1);
int head= 1, tail= 1, ans= 1;
ansMax= dp[1][0], ansMin= dp[1][0];
while( head<= tail && tail<= n ){
if( ansMax- ansMin<= m ){
ans= max( ans, tail- head+ 1 );
tail++;
ansMax= max( ansMax, dp[tail][0] );
ansMin= min( ansMin, dp[tail][0] );
}
else{
++head;
ansMin= inf, ansMax= -inf;
query( head, tail, 1, n, 1 );
}
if( n- head+ 1< ans ) break;
}
printf("%d\n", ans );
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
用Java代码实现POJ(PKU)上题2494!
PKU2104的源代码,高级数据结构线段树的应用之一:找数据。
acm 1001 到1009代码,已通过验证
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
acm pku poj 1000 1001 1002 1003 1201
O(nlogn)凸包问题 poj2187
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
DAG上的记忆化树形DP,博弈 有限状态自动机+树形DP 状态压缩DP 炮兵阵地 Help Bob,买匹萨 匹配数量 堆筛子 全排列式状态DP 计算几何 多边形地图染色 数据结构 Hash 枚举+hash,方程解数 点集对称中心 字符...
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
pku 123 题目代码 pku acm poj
基于Python的北京大学/北大/PKU 智慧场馆 场地预约 自动化 +源代码+文档说明 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分...
poi3252,北大acm里面的题目代码。
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。 “北京大学程序在线评测系统”是一个免费的公益...
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
pku 2761(求区间内第k小的数) 我是用线段树去做的,好像也可用树状数组做的,稍微有一点注释在里面的^_^