本文共 1918 字，大约阅读时间需要 6 分钟。
http://acm.hdu.edu.cn/showproblem.php?pid=4123
给出一棵树，一个人从一个点开始跑，会跑到尽量远的叶子节点，现在问对于每一个询问q，最多能有多少标号连续的人跑，满足最长者减最短者不超过q。
这道题综合了三层，树的最远对，rmq，和单调队列。
首先尽量远就是要最远对，用直径的算法。然后是对于每一个q，从1～n作为右端点，用单调队列的思想求最长的区间，每次查询是否到达q一定要用rmq，我用线段树做，开始debug半天发现rt必须从1开始，后来又发现超时。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,k,n) for(int i=n;i>=k;i--)#define Lson (u<<1)#define Rson ((u<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define NEG(a) memset(a,-1,sizeof(a));#define FILL(a) memset(a,0x3f,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define print(b,a) cout< <<"="<< e[maxn];void init(){ For(i,1,N) e[i].clear(); NEG(f);NEG(g);NEG(h);NEG(longest);}int dfs(int root, int pre){ int est = 0, esti=-1, er=0; if(f[root]!=-1) return f[root]; if(e[root].empty()) { //printf("root=%d\n",root); return f[root] = 0; } int sz=e[root].size(); for(int i=0;i est){ est = f[e[root][i].v]+e[root][i].w; esti = i; } } } longest[root] = esti; sz=e[root].size(); for(int i=0;i er&&i!=longest[root]){ er = f[e[root][i].v]+e[root][i].w; } } } g[root] = er; return f[root] = est;}void dfs1(int root, int pre){ int sz=e[root].size(); for(int i=0;i <= N;i++) { mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp1[i][0] = a[i]; dp2[i][0] = a[i]; } for(int j = 1;j <= mm[N];j++) for(int i = 1;i + (1< Q) id++; ans=max(ans,j-id+1); } printf("%d\n",ans); }}int main(){ // fp; while(scanf("%d%d",&N,&M)==2&&!(N==0&&M==0)) { init(); For(i,1,N-1) { int u,v,w; scanf("%d %d %d",&u,&v,&w); e[u].push_back(edge{v,w}); e[v].push_back(edge{u,w}); } solve(); } return 0;}
转载于:https://www.cnblogs.com/diang/p/5734695.html
