首页 > 代码库 > hdu3804（树链剖分）
hdu3804（树链剖分）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3804
题意：给定一棵n个结点的树及边权，回答m个询问（x，y）满足以下条件的边权：
1）该边在结点1~x的路径上。
2）在1~x的路径上小于等于y的最大边权。
分析：离线处理，将边权和询问的y值按从小到大排序，然后逐序将边权插入线段树中，每次查询当前条件下路径上的最大值（线段树维护）就是答案。。。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 10007#define inf 0x3f3f3f3f#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;struct edge{ int to,next; edge(){} edge(int to,int next):to(to),next(next){}}e[N<<1];int head[N<<1],tot;int top[N];//top[v]表示v所在的重链的顶端节点int fa[N];//父亲节点int dep[N];//深度int sz[N];//si[v]表示以v为根节点的子树的节点数int son[N];//重儿子int p[N];//p[v]表示v与其父亲节点的连边在线段树中的位置int fp[N];//与p数组相反int pos;//所有链构成的线段树总长度int mx[N<<2];struct Edge{ int u,v,w,id; bool operator<(const Edge &a)const { return w<a.w; }}E[N<<1];struct Query{ int x,y,id; bool operator<(const Query &a)const { return y<a.y; }}q[N];void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void init(){ tot=0;FILL(head,-1); pos=0;FILL(son,-1);}void dfs(int u,int f,int d){ sz[u]=1;dep[u]=d;fa[u]=f; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f)continue; dfs(v,u,d+1); sz[u]+=sz[v]; if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v; }}void getpos(int u,int sp){ top[u]=sp; p[u]=++pos; fp[pos]=u; if(son[u]==-1)return; getpos(son[u],sp); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v!=son[u]&&v!=fa[u]) { getpos(v,v); } }}void Pushup(int rt){ int ls=rt<<1,rs=ls|1; mx[rt]=max(mx[ls],mx[rs]);}void update(int ps,int c,int l,int r,int rt){ if(l==r) { mx[rt]=c; return; } int m=(l+r)>>1; if(ps<=m)update(ps,c,lson); else update(ps,c,rson); Pushup(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return mx[rt]; int m=(l+r)>>1; int res=-inf; if(L<=m)res=max(res,query(L,R,lson)); if(m<R)res=max(res,query(L,R,rson)); return res;}int lca(int u,int v){ int fu=top[u],fv=top[v]; int res=-1; while(fu!=fv) { if(dep[fu]<dep[fv]) { swap(fu,fv);swap(u,v); } res=max(res,query(p[fu],p[u],1,pos,1)); u=fa[fu];fu=top[u]; } if(dep[u]>dep[v])swap(u,v); if(u!=v) res=max(res,query(p[son[u]],p[v],1,pos,1)); return res;}int ans[N];int main(){ int T,n,m,x,y; int a,b,c; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,b); addedge(b,a); E[i].u=a;E[i].v=b; E[i].w=c;E[i].id=i; } dfs(1,0,0); getpos(1,1); for(int i=1;i<n;i++) if(dep[E[i].u]>dep[E[i].v]) swap(E[i].u,E[i].v); sort(E+1,E+n); scanf("%d",&m); for(int i=0;i<m;i++)scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i; sort(q,q+m);FILL(mx,-1); for(int j=1,i=0;i<m;i++) { while(j<n&&E[j].w<=q[i].y) { update(p[E[j].v],E[j].w,1,pos,1); j++; } ans[q[i].id]=lca(1,q[i].x); } for(int i=0;i<m;i++)printf("%d\n",ans[i]); }}
hdu3804（树链剖分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。