本文共 2383 字，大约阅读时间需要 7 分钟。
题目：求出一棵树上任意一点能到的最远距离，然后若干询问，问区间内最大最小距离只差小于ｑ的区间最长有多长。
思路：最远距离通过两次ｄｆｓ树形ｄｐ求得，询问需要先用ｓｔ表处理一下，然后线性扫。基本是参考ｋｕａｎｇｂｉｎ的。
ps:可能是我写挫了。。用ｖｅｃｔｏｒ做邻接表是１９９６ｍｓ过了一次，然后就是无限ｔｌｅ。。。。不得不改成手写链表才搞到１５００ｍｓ。。。ｖｅｃｔｏｒ感觉不能随便用了啊。。。。。。
http://www.cnblogs.com/kuangbin/archive/2013/11/08/3414812.html
#include #include #include #include #include #include #include #include #include #include #include #include #define pb push_back#define fs first#define se second#define sq(x) (x)*(x)#define eps 0.0000000001#define IINF (1<<30)#define clr(x) memset((x),0,sizeof (x))using namespace std;typedef long long ll;typedef pair P;const int maxv=5e4+300;int N,M;struct EDGE{ int t,d; EDGE *nt;}pool[maxv*3];int ph=0;EDGE *newedge(){ pool[ph].nt=NULL; return &pool[ph++];}EDGE *head[maxv],*tail[maxv];int maxd[maxv],maxdn[maxv],smaxd[maxv],smaxdn[maxv];void addedge(int x,int y,int z){ tail[x]->nt=newedge(); tail[x]=tail[x]->nt; tail[x]->t=y,tail[x]->d=z;}void dfs1(int v,int fa){ for(EDGE *i=head[v]->nt;i!=NULL;i=i->nt){ int u=i->t; int len=i->d; if(u==fa) continue; dfs1(u,v); if(maxd[u]+len>smaxd[v]){ smaxd[v]=maxd[u]+len; smaxdn[v]=u; if(smaxd[v]>maxd[v]){ swap(smaxd[v],maxd[v]); swap(smaxdn[v],maxdn[v]); } } }}void dfs2(int v,int fa){ for(EDGE *i=head[v]->nt;i!=NULL;i=i->nt){ int u=i->t; int len=i->d; if(u==fa) continue; if(u==maxdn[v]){ if(smaxd[v]+len>smaxd[u]){ smaxd[u]=smaxd[v]+len; smaxdn[u]=v; if(smaxd[u]>maxd[u]){ swap(smaxd[u],maxd[u]); swap(smaxdn[u],maxdn[u]); } } }else{ if(maxd[v]+len>smaxd[u]){ smaxd[u]=maxd[v]+len; smaxdn[u]=v; if(smaxd[u]>maxd[u]){ swap(smaxd[u],maxd[u]); swap(smaxdn[u],maxdn[u]); } } } dfs2(u,v); }}ll STmin[maxv][30];ll STmax[maxv][30];void makeST(){ memset(STmin,0x3f,sizeof STmin); memset(STmax,0,sizeof STmax); for(int i=1;i<=N;i++){ STmin[i][0]=STmax[i][0]=maxd[i]; } for(int k=1;k<25;k++){ for(int i=1;i+(1< <=N+1;i++){ STmin[i][k]=min(STmin[i][k-1],STmin[i+(1<<(k-1))][k-1]); STmax[i][k]=max(STmax[i][k-1],STmax[i+(1<<(k-1))][k-1]); } }}int getdif(int l,int r){ int k=0; while((1<<(k+1)) nt=NULL; tail[i]=head[i]; }}int main(){ freopen("/home/files/CppFiles/in","r",stdin); /* std::ios::sync_with_stdio(false); std::cin.tie(0);*/ while(cin>>N>>M){ if(N==0&&M==0) break; init(); for(int i=0;i
转载于:https://www.cnblogs.com/Cw-trip/p/4700852.html
