bzoj3307雨天的尾巴

Forever_goodboy Forever_goodboy     2022-09-25     366

关键词:

3307: 雨天的尾巴

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

N个点,形成一个树状结构。有M次发放,每次选择两个点x,y
对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成
所有发放后,每个点存放最多的是哪种物品。

Input

第一行数字N,M
接下来N-1行,每行两个数字a,b,表示a与b间有一条边
再接下来M行,每行三个数字x,y,z.如题

Output

 

输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种,如果有
多种物品的数量一样,输出编号最小的。如果某个点没有物品
则输出0

Sample Input

20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50

Sample Output

87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50


1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10^9
 
 solution:
      这题其实很好想,利用差分思想在x,y的权值线段树里z的位置上+1,lca和fa[lca]的位置上-1,每次合并一下线段树就好。
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define mid (l+r>>1)
 7 #define N 100010
 8 int read() {
 9     int s=0,f=1;
10     char ch=getchar();
11     for( ; ch<0||ch>9; f=(ch==-)?-1:f,ch=getchar()) ;
12     for( ; ch>=0&&ch<=9; s=s*10+(ch^48),ch=getchar()) ;
13     return s*f;
14 }
15 int n,m,tot,cnt,num;
16 int r[N],p[19][N],deep[N],root[N],Hash[N];
17 int mx[N*50],ord[N*50],ls[N*50],rs[N*50];
18 struct node {
19     int X,Y,Z;
20     friend bool operator < (node a,node b) {return a.Z<b.Z;}
21 } q[N];
22 struct EDGE{int to,next;} c[N<<1];
23 void add(int a,int b) {
24     c[++tot]=(EDGE){b,r[a]},r[a]=tot;
25 }
26 void dfs(int x) {
27     for(int i=r[x]; ~i; i=c[i].next) if(c[i].to!=p[0][x]) p[0][c[i].to]=x,deep[c[i].to]=deep[x]+1,dfs(c[i].to);
28 }
29 int lca(int a,int b) {
30     if(deep[a]<deep[b]) swap(a,b);
31     for(int i=18; i>=0; --i) if(deep[p[i][a]]>=deep[b]) a=p[i][a];
32     if(a==b) return a;
33     for(int i=18; i>=0; --i) if(p[i][a]!=p[i][b]) a=p[i][a],b=p[i][b];
34     return p[0][a];
35 }
36 void pushup(int x) {
37     mx[x]=max(mx[ls[x]],mx[rs[x]]);
38     ord[x]=(mx[ls[x]]>=mx[rs[x]])?ord[ls[x]]:ord[rs[x]];
39 }
40 void update(int &x,int a,int b,int l,int r) {
41     if(!x) x=++cnt;
42     if(l==r) {mx[x]+=b,ord[x]=Hash[l];return ;}
43     if(a<=mid) update(ls[x],a,b,l,mid);
44     else update(rs[x],a,b,mid+1,r);
45     pushup(x);
46 }
47 void Merge(int &a,int b,int l,int r) {
48     if(!b) return ;
49     if(!a) {a=b;return ;}
50     if(l==r) {mx[a]+=mx[b];return ;}
51     Merge(ls[a],ls[b],l,mid),Merge(rs[a],rs[b],mid+1,r);
52     pushup(a);
53 }
54 void M(int u) {for(int i=r[u]; ~i; i=c[i].next) if(c[i].to!=p[0][u]) M(c[i].to),Merge(root[u],root[c[i].to],1,m);}
55 int main() {
56     n=read(),m=read();
57     memset(r,0xff,sizeof(r));
58     for(int i=1; i<=n; ++i)  root[i]=++cnt;
59     for(int a,b,i=1; i<n; ++i) a=read(),b=read(),add(a,b),add(b,a);
60     deep[1]=1,dfs(1);
61     for(int j=1; (1<<j)<=n; j++) for(int i=1; i<=n; ++i) p[j][i]=p[j-1][p[j-1][i]];
62     for(int i=1; i<=m; ++i) q[i].X=read(),q[i].Y=read(),Hash[i]=q[i].Z=read();
63     sort(q+1,q+m+1);  sort(Hash+1,Hash+m+1); num=unique(Hash+1,Hash+m+1)-Hash;
64     for(int a,b,LCA,d=0,i=1; i<=m; ++i) {
65         a=q[i].X,b=q[i].Y,LCA=lca(a,b);
66         d=lower_bound(Hash+1,Hash+num,q[i].Z)-Hash;
67         update(root[a],d,1,1,m),update(root[b],d,1,1,m),update(root[LCA],d,-1,1,m);
68         if(LCA!=1)  update(root[p[0][LCA]],d,-1,1,m);
69     } M(1);
70     for(int i=1; i<=n; ++i) printf("%d
",ord[root[i]]);
71     return 0;
72 }

 

bzoj3307雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBDescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。... 查看详情

bzoj3307:雨天的尾巴(代码片段)

传送门树上差分+线段树合并+离散化对于修改的路径,树上差分就好了代码:#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情

bzoj3307雨天的尾巴

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势:人工栈(好像也不难啊喂)我们发现对于每种物品,只需要在u这地方的权值线段树上+1,v的权值线段树上+1,LC... 查看详情

bzoj-3307:雨天的尾巴

咱可以差分一下,把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$,$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询,最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了,$RE$了一次。1#include<cassert>2#inclu... 查看详情

bzoj3307雨天的尾巴

题目链接:传送门题目大意:中文题,略题目思路:网上有题解说是合并线段树的,但是太难蒟蒻不会,只能用树剖求解     如果不是树而是一维数组我们会怎么解?        当然是利用前缀和思想标记(... 查看详情

bzoj3307雨天的尾巴线段树合并

​​http://www.elijahqi.win/archives/3463​​​DescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。Input第一行数字N,... 查看详情

bzoj3307雨天的尾巴(可持久化线段树合并)(代码片段)

题目大意:一颗树,想要在树链上添加同一物品,问最后每个点上哪个物品最多。解题思路:假如说物品数量少到可以暴力添加,且树点极少,我们怎么做。首先在一个树节点上标记出哪些物品有多少,寻找道路上的节点暴力添... 查看详情

[bzoj3307]雨天的尾巴(代码片段)

DescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。Input第一行数字N,M接下来N-1行,每行两个数字a,b,表示a与b... 查看详情

考后反思(bzoj3940bzoj4899bzoj3307)(代码片段)

...来想用哈希只可以得20左右没想到由于数据过于水A了然后雨天的尾巴骗了5分,总分105我太菜了首先时间分配的不合理:第一题大水题ac自动机打完了都不会,第二题略微想了想打了个高斯消元,然后样例没过......,最后输出了一... 查看详情

[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 查看详情

gdoi模拟雨天的尾巴树套树

雨天的尾巴深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的... 查看详情

gdoi模拟雨天的尾巴树套树

雨天的尾巴深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的... 查看详情

雨天的尾巴(代码片段)

考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程:当时想到了离散化(很慌没打出来。。。),树上差分,lca倍增,当时觉滴倍增很难打,一看n<100000,于是选择用向上标记法,然而少了一行代码,,,,爆... 查看详情

gdoi2014模拟雨天的尾巴(代码片段)

题目深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被... 查看详情

[vani有约会]雨天的尾巴(代码片段)

我之前考试是遇到过这题,但是数据范围k<=20,状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并:比如两个相同大小的线段树,将b树各个区间上的值合并到a树上,从树根开始合并,然后递归合并左右... 查看详情

luogu4556雨天的尾巴(线段树合并+差分)(代码片段)

题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮... 查看详情

luogu4556雨天的尾巴树上差分线段树合并(代码片段)

传送门 一个套路题……树上差分+线段树合并即可注意一个细节:$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$,否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码,因为这份代码没有卡空... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并)(代码片段)

传送门一道线段树合并首先不难看出树上差分我们把每一次修改拆成四个,在(u,v)分别放上一个,在(lca)和(fa[lca])各减去一个,那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的,那么线段... 查看详情