关键词:
雨天的尾巴
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。
首先村落里的一共有n 座房屋,并形成一个树状结构。然后救济粮分m 次发放,每次选择两个房屋(x,y),然后对于x 到y 的路径上(含x 和y) 每座房子里发放一袋z 类型的救济粮。
然后深绘里想知道,当所有的救济粮发放完毕后,每座房子里存放的最多的是哪种救济粮。
输入格式:
第一行两个正整数n,m,含义如题目所示。接下来n-1 行,每行两个数(a,b),表示(a,b) 间有一条边。
再接下来m 行,每行三个数(x,y,z),含义如题目所示。
输出格式:
n 行,第i 行一个整数,表示第i 座房屋里存放的最多的是哪种救济粮,如果有多种救济粮存放次数一样,输出编号最小的。
如果某座房屋里没有救济粮,则对应一行输出0。
样例输入:
5 3
1 2
3 1
3 4
5 4
2 3 3
1 5 2
3 3 3
样例输出:
2
3
3
0
2
数据范围:
对于20% 的数据,1 <= n;m <= 100对于50% 的数据,1 <= n;m <= 2000
对于100% 的数据,1 <= n; m<= 100000; 1 <= a; b; x; y <= n; 1 <= z<=10^9
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int N=100005; 5 const int M=20000005; 6 int Head[N],Next[N*2],V[N*2],cnt=0;//store the tree structure before DFS 7 int Ans[N],ST[N][17],dep[N],F[N];//store the DP data for ST to get LCA 8 int lch[M],rch[M],size,key[M];//store the inner tree----key[] records the maximum of the food.same.count() 9 int Hash[N],n;//z can be as big as 10^9 so hash can condense it to an acceptable range 10 inline void Link(int x,int y) 11 { 12 cnt++; 13 V[cnt]=y; 14 Next[cnt]=Head[x]; 15 Head[x]=cnt; 16 } 17 inline void Dfs(int x,int f,int D) 18 { 19 dep[x]=D; 20 F[x]=f; 21 ST[x][0]=f; 22 for(int i=1;i<=16;i++) 23 { 24 if(dep[x]-(1<<i)>=1) ST[x][i]=ST[ST[x][i-1]][i-1]; 25 else break; 26 } 27 for(int i=Head[x];i;i=Next[i]) if(V[i]!=f) Dfs(V[i],x,D+1); 28 } 29 inline int LCA(int x,int y) 30 { 31 if(dep[x]>dep[y]) 32 { 33 for(int i=16;i>=0;i--) if(dep[ST[x][i]]>=dep[y]) x=ST[x][i]; 34 } 35 else if(dep[y]>dep[x]) 36 { 37 for(int i=16;i>=0;i--) if(dep[ST[y][i]]>=dep[x]) y=ST[y][i]; 38 }//move x and y to the same depth 39 if(x==y) return x; 40 for(int i=16;i>=0;i--) 41 { 42 if(ST[y][i]!=ST[x][i]) 43 { 44 y=ST[y][i]; 45 x=ST[x][i]; 46 } 47 } 48 return F[x]; 49 } 50 inline int Find_Space(int x) 51 { 52 int p=x%N; 53 while(Hash[p]!=x&&Hash[p]!=0) 54 { 55 p++; 56 if(p==N) p=0; 57 } 58 if(!Hash[p]) Hash[p]=x; 59 return p; 60 } 61 inline void Insert(int &x,int l,int r,int num,int k) 62 { 63 if(x==0) x=++size; 64 if(l==r) 65 { 66 key[x]+=k; 67 return; 68 } 69 int mid=(l+r)>>1; 70 if(num<=mid) Insert(lch[x],l,mid,num,k); 71 else Insert(rch[x],mid+1,r,num,k); 72 key[x]=max(key[lch[x]],key[rch[x]]); 73 } 74 inline void Merge(int p,int fp,int l,int r) 75 { 76 if(l==r) 77 { 78 key[fp]+=key[p]; 79 return; 80 } 81 int mid=(l+r)>>1; 82 if(lch[p]) 83 { 84 if(!lch[fp]) lch[fp]=lch[p]; 85 else Merge(lch[p],lch[fp],l,mid); 86 } 87 if(rch[p]) 88 { 89 if(!rch[fp]) rch[fp]=rch[p]; 90 else Merge(rch[p],rch[fp],mid+1,r); 91 } 92 key[fp]=max(key[lch[fp]],key[rch[fp]]); 93 } 94 inline int Query(int p,int l,int r) 95 { 96 if(!p) return 0; 97 if(l==r) return l; 98 int mid=(l+r)>>1; 99 if(key[lch[p]]>=key[rch[p]]) 100 { 101 if(key[lch[p]]>0) return Query(lch[p],l,mid); 102 else return 0; 103 } 104 else 105 { 106 if(key[rch[p]]>0) return Query(rch[p],mid+1,r); 107 else return 0; 108 } 109 } 110 inline void Reply(int x) 111 { 112 for(int i=Head[x];i;i=Next[i]) if(V[i]!=F[x]) 113 { 114 Reply(V[i]); 115 Merge(V[i],x,1,N);//merge the zone tree to its outer father‘s zone tree 116 } 117 Ans[x]=Query(x,1,N); 118 } 119 int main() 120 { 121 int m,x,y,z,anc; 122 scanf("%d%d",&n,&m); 123 size=n*2; 124 for(int i=1;i<n;i++) 125 { 126 scanf("%d%d",&x,&y); 127 Link(x,y); 128 Link(y,x); 129 } 130 Dfs(1,0,1); 131 while(m--) 132 { 133 scanf("%d%d%d",&x,&y,&z); 134 z=Find_Space(z); 135 anc=LCA(x,y); 136 Insert(x,1,N,z,1); 137 Insert(y,1,N,z,1); 138 Insert(anc,1,N,z,-1); 139 if(F[anc]) Insert(F[anc],1,N,z,-1); 140 } 141 Reply(1); 142 for(int i=1;i<=n;i++) printf("%d ",Hash[Ans[i]]); 143 return 0; 144 }
gdoi2014模拟雨天的尾巴(代码片段)
题目深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被... 查看详情
树套树
树套树,顾名思义,就是用一颗树套在另外一组树之上。比方说我们有一颗树,假如它的每一个结点(抽象意义上,一株树由多个结点组成)也是一株树,那么这就形成了树套树。外部树和内部树可以是不同品种的。一般外... 查看详情
「模板」树套树
「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过,但我删除SBT点的时候没回收内存!写了就RE!先放上来吧,回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情
bzoj3307:雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 479 Solved: 214[Submit][Status][Discuss]DescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的 查看详情
[bzoj3307]雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 709 Solved: 296[Submit][Status][Discuss]DescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的 查看详情
树套树(代码片段)
树套树一种思想,就是一棵树的节点是另一颗树。在外面的叫外层树,在里面的叫内层树。外层树一般是,树状数组,线段树内层树一般是平衡树,STL,线段树线段树套STL/**@Author:zhl*@Date:2020-11-1612:50:32*/#include<bits/stdc++.h>#define... 查看详情
[luogu4556]雨天的尾巴(代码片段)
[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情
树套树三题题解
...这题数据非常水……从O(nlogn)的主席树到O(nlog3n)的树套树+二分到O(nsqrt(n)log2n)的分块套二分套二分到O(n2)的暴力都能过……)鉴于这就是动态排名系统的静态版,就不说了,贴代码:线段树套平衡树:#include 查看详情
bzoj3307雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBDescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。... 查看详情
树套树初探(代码片段)
最近学了学树套树,做了几道模板题。发现好像有点水咳咳咳。树套树,顾名思义,一个树套一个树。比如树状数组套平衡树,就是把树状数组的每一个结点作为一颗平衡树,线段树套权值线段树,就是一颗线段树,每一个结点... 查看详情
uvalive-6709树套树(代码片段)
...法:暴力可过,建n颗线段树暴力更新,但是正解应该是树套树,树套树需要注意的是当建树或修改时pushup操作不能直接搞,要先判断是不是外面层的叶子节点,如果是直接修改,如果不是,应该是从外面层的对应子节点更新过... 查看详情
树套树乱讲
树套树乱讲树状数组套线段树先学会主席树。主席树可以被理解为一个二维平面,其中n棵树可以视作横轴,每棵树中的坐标范围(也就是线段树的坐标范围)可以视作纵轴。这样一来就是用主席树维护了一些在二维平面上的点... 查看详情
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异,敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先,明确一下Splay套线段树用来处理什么问题。它可以支持:插入x,删除x,单点修改,查询x在区间[l,r]的排名,查询区间[l,r]中排名为k的数,以及一个数在区间[l,r]中... 查看详情
bzoj3307:雨天的尾巴(代码片段)
传送门树上差分+线段树合并+离散化对于修改的路径,树上差分就好了代码:#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情
洛谷p3380模板二逼平衡树(树套树)
洛谷P3380【模板】二逼平衡树(树套树)线段树套treap:就是线段树每个节点放一个treap。建树复杂度应该是$nlogn$,操作1,3,4,5的复杂度是$(logn)^2$,操作2的复杂度是$(logn)^3$。操作3:找到线段树的对应叶子节点后找到要删除的值,... 查看详情
bzoj-3307:雨天的尾巴
咱可以差分一下,把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$,$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询,最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了,$RE$了一次。1#include<cassert>2#inclu... 查看详情
[bzoj720][jzyzoj2016]gty的妹子树强制在线树分块/树套树
jzyzoj的p2016先码着,强制在线的树分块或者树套树?关键是我树分块还在入门阶段树套树完全不会啊摔 http://blog.csdn.net/jiangyuze831/article/details/41445003果然我除了抄代码什么也不会......树分块之类的东西完全不会计算复杂度.....似... 查看详情