[Vani有约会]雨天的尾巴
2018-09-05 07:42:50来源:博客园 阅读 ()
我之前考试是遇到过这题,但是数据范围k<=20,状压就能过。
结果原题范围k<=100000……
果断线段树合并。
普及线段树合并:
比如两个相同大小的线段树,将b树各个区间上的值合并到a树上,从树根开始合并,然后递归合并左右儿子,有三种情况:
(假设现在a树遍历到x点,b树遍历到y点)
1.x,y至少其一未被修改过(语文不好勿喷),则将x变为遍历过的那个。
2.x,y位于叶节点(l==r),则sum[x]+=sum[y]。
3.一般情况,递归处理左右儿子,最后更新当前点。
本题中合并如下:
void merge(int &a,int b,int l,int r) { if(!b)return ; if(!a){a=b;return ;} //1 if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}//注意维护 //2 int mid = (l+r)>>1; merge(ls[a],ls[b],l,mid);//递归左子树 merge(rs[a],rs[b],mid+1,r);//递归右子树 update(a); //3 }
juruo代码奉上:
#include<cstdio> #include<algorithm> using namespace std; #define N 100105 inline int rd() { int f=1,c=0;char ch = getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n,m,hed[N],cnt; struct eg { int to; int nxt; }e[2*N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } int dep[N],fa[N],son[N],tp[N],siz[N]; void dfs1(int u) { dep[u]=dep[fa[u]]+1; siz[u]=1; for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to==fa[u])continue; fa[to]=u; dfs1(to); siz[u]+=siz[to]; if(siz[to]>siz[son[u]])son[u]=to; } } void dfs2(int u,int topn) { tp[u]=topn; if(!son[u])return ; dfs2(son[u],topn); for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to==fa[u]||to==son[u])continue; dfs2(to,to); } } int get_lca(int a,int b) { while(tp[a]!=tp[b]) { if(dep[tp[a]]<dep[tp[b]])swap(a,b); a=fa[tp[a]]; } return dep[a]<dep[b]?a:b; } int rt[N],sum[70*N],sn[70*N],ls[70*N],rs[70*N],tot; void update(int u) { sn[u]=sum[ls[u]]>=sum[rs[u]]?sn[ls[u]]:sn[rs[u]]; sum[u]=sum[ls[u]]>=sum[rs[u]]?sum[ls[u]]:sum[rs[u]]; } void insert(int l,int r,int &u,int qx,int d) { if(!u)u=++tot; if(l==r) { sum[u]+=d; if(sum[u])sn[u]=l; else sn[u]=0; return ; } int mid = (l+r)>>1; if(qx<=mid)insert(l,mid,ls[u],qx,d); else insert(mid+1,r,rs[u],qx,d); update(u); } void merge(int &a,int b,int l,int r) { if(!b)return ; if(!a){a=b;return ;} if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;} int mid = (l+r)>>1; merge(ls[a],ls[b],l,mid); merge(rs[a],rs[b],mid+1,r); update(a); } int ans[N]; void dfs(int u) { for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to==fa[u])continue; dfs(to); merge(rt[u],rt[to],1,m); } ans[u]=sn[rt[u]]; } struct ND { int f,t,z; }nd[N]; bool cmp(ND a,ND b) { return a.z<b.z; } int to[N]; int main() { n=rd(),m=rd(); for(int f,t,i=1;i<n;i++) { f=rd(),t=rd(); ae(f,t),ae(t,f); } dfs1(1),dfs2(1,1); for(int f,t,z,i=1;i<=m;i++) { f=rd(),t=rd(),z=rd(); nd[i].f=f,nd[i].t=t,nd[i].z=z; } sort(nd+1,nd+1+m,cmp); int las=-1,k=0; for(int f,t,z,lca,i=1;i<=m;i++) { if(nd[i].z!=las) { las=nd[i].z; to[++k]=nd[i].z; } nd[i].z=k; f = nd[i].f,t = nd[i].t,z = nd[i].z; lca = get_lca(f,t); insert(1,m,rt[f],z,1); insert(1,m,rt[t],z,1); insert(1,m,rt[lca],z,-1); if(lca!=1)insert(1,m,rt[fa[lca]],z,-1); } dfs(1); for(int i=1;i<=n;i++) { printf("%d\n",to[ans[i]]); } return 0; }
在这里提一下空间问题:
每进行一次插入,会添加log级的点,因此juruo认为开nlogn级数组即可。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ 1061 青蛙的约会 扩展欧几里得 2018-06-17
- 洛谷P1516 青蛙的约会 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash