正文 

当前位置： 首页 > java > java教程

bzoj3307:雨天的尾巴

OldJang OldJang     2022-08-26     270

关键词：

3307: 雨天的尾巴

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 479  Solved: 214
[Submit][Status][Discuss]

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

 

题解

这题有点奥妙重重啊……我数组开大了不到十分之一就卡着内存过了

考虑每种颜色，我们可以树上差分，x,y处+1，xy的lca处-1，lca的father-1，然后子树和就是颜色在这个点的数量。然后我们用一个线段树来维护每个节点所有的颜色的值（这个用差分做）和他们的最大值，然后从底向上一路线段树合并上去就行了

  1 program j01;
  2 const maxn=100086;
  3 type xx=record l,r,mx,id:longint; end;
  4      lsh=record id,w:longint; end;
  5 var head:array[0..maxn]of longint;
  6     q,next:array[0..2*maxn]of longint;
  7     t:array[0..65*maxn]of xx;
  8     st:array[0..20,0..2*maxn]of longint;
  9     dep,fir,dfn,fa,root:array[0..maxn]of longint;
 10     tot,dfnt,tt,n,m,u,v,w,cnt,lc,p,i,mx:longint;
 11     op:array[0..maxn]of record u,v,w:longint;end;
 12     ls:array[0..maxn]of lsh;
 13     bin,ps:array[0..maxn]of longint;
 14     ans:array[0..maxn]of longint;
 15 
 16 procedure swap(var a,b:longint);
 17 var c:longint;
 18 begin
 19   c:=a;a:=b;b:=c;
 20 end;
 21 
 22 procedure add(u,v:longint);
 23 begin
 24   inc(tt);q[tt]:=v;next[tt]:=head[u];head[u]:=tt;
 25 end;
 26 
 27 procedure dfs(i,pre:longint);
 28 var j:longint;
 29 begin
 30   inc(tot);st[0,tot]:=i;fir[i]:=tot;
 31   inc(dfnt);dfn[dfnt]:=i;
 32   j:=head[i];
 33   while j>0 do
 34   begin
 35     if(q[j]<>pre)then
 36     begin
 37       dep[q[j]]:=dep[i]+1;fa[q[j]]:=i;
 38       dfs(q[j],i);
 39       inc(tot);st[0,tot]:=i;
 40     end;
 41     j:=next[j];
 42   end;
 43 end;
 44 
 45 function min_st(a,b:longint):longint;
 46 begin
 47   if dep[a]<dep[b] then exit(a) else exit(b);
 48 end;
 49 
 50 procedure getst;
 51 var i,j:longint;
 52 begin
 53   bin[1]:=0;
 54   for i:=2 to tot do
 55     if i and(i-1)=0 then bin[i]:=bin[i-1]+1 else bin[i]:=bin[i-1];
 56   for i:=1 to bin[tot] do
 57     for j:=1 to tot+1-(1 shl i) do
 58       st[i,j]:=min_st(st[i-1,j],st[i-1,j+(1 shl(i-1))]);
 59 end;
 60 
 61 function lca(u,v:longint):longint;
 62 var k:longint;
 63 begin
 64   if u=v then exit(u);
 65   u:=fir[u];v:=fir[v];
 66   if u>v then swap(u,v);k:=bin[v-u];
 67   exit(min_st(st[k,u],st[k,v+1-(1 shl k)]));
 68 end;
 69 
 70 procedure update(i:longint);
 71 begin
 72   if t[t[i].l].mx>=t[t[i].r].mx then
 73   begin
 74     t[i].mx:=t[t[i].l].mx;t[i].id:=t[t[i].l].id;
 75   end else
 76   begin
 77     t[i].mx:=t[t[i].r].mx;t[i].id:=t[t[i].r].id;
 78   end;
 79   if t[i].mx=0 then t[i].id:=0;
 80 end;
 81 
 82 procedure ins(var i:longint;l,r,ps,dd:longint);
 83 var mid:longint;
 84 begin
 85   if i=0 then
 86   begin
 87     inc(cnt);i:=cnt;
 88   end;
 89   if l=r then
 90   begin
 91     inc(t[i].mx,dd);t[i].id:=l;exit;
 92   end;
 93   mid:=(l+r)div 2;
 94   if ps<=mid then ins(t[i].l,l,mid,ps,dd) else ins(t[i].r,mid+1,r,ps,dd);
 95   update(i);
 96 end;
 97 
 98 function merge(x,y,l,r:longint):longint;
 99 var mid:Longint;
100 begin
101   if(x=0)or(y=0)then exit(x+y);
102   if l=r then
103   begin
104     inc(t[x].mx,t[y].mx);t[x].id:=l;exit(x);
105   end;
106   mid:=(l+r)div 2;
107   t[x].l:=merge(t[x].l,t[y].l,l,mid);
108   t[x].r:=merge(t[x].r,t[y].r,mid+1,r);
109   update(x);exit(x);
110 end;
111 
112 procedure qsort(l,r:longint);
113 var i,j,x:longint;y:lsh;
114 begin
115   i:=l;j:=r;x:=ls[(i+j)div 2].w;
116   repeat
117     while ls[i].w<x do inc(i);
118     while x<ls[j].w do dec(j);
119     if i<=j then
120     begin
121       y:=ls[i];ls[i]:=ls[j];ls[j]:=y;
122       inc(i);dec(j);
123     end;
124   until i>j;
125   if i<r then qsort(i,r);
126   if l<j then qsort(l,j);
127 end;
128 
129 procedure disc;
130 var i:longint;
131 begin
132   qsort(1,m);
133   op[ls[1].id].w:=1;mx:=1;
134   ps[1]:=ls[1].w;
135   for i:=2 to m do
136   begin
137     if ls[i].w<>ls[i-1].w then inc(mx);
138     op[ls[i].id].w:=mx;
139     ps[mx]:=ls[i].w;
140   end;
141 end;
142 
143 begin
144   readln(n,m);
145   fillchar(head,sizeof(head),0);tt:=0;
146   for i:=1 to n-1 do
147   begin
148     readln(u,v);add(u,v);add(v,u);
149   end;
150   dfs(1,0);
151   getst;
152   for i:=1 to m do
153   begin
154     readln(op[i].u,op[i].v,op[i].w);
155     ls[i].w:=op[i].w;ls[i].id:=i;
156   end;
157   disc;
158   for i:=1 to m do
159   begin
160     u:=op[i].u;v:=op[i].v;w:=op[i].w;
161     lc:=lca(u,v);
162     ins(root[u],1,mx,w,1);
163     ins(root[v],1,mx,w,1);
164     ins(root[lc],1,mx,w,-1);
165     if fa[lc]<>0 then ins(root[fa[lc]],1,mx,w,-1);
166   end;
167   for i:=n downto 1 do
168   begin
169     p:=dfn[i];
170     ans[p]:=ps[t[root[p]].id];
171     if fa[p]>0 then root[fa[p]]:=merge(root[fa[p]],root[p],1,mx);
172   end;
173   for i:=1 to n do writeln(ans[i]);
174 end.

 

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])各减去一个，那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段... 查看详情