雨天的尾巴 bzoj-3307

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

想法:我们像主席树一样,维护桶然后对应节点合并即可。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100050
using namespace std;
int t[N*60],n,m,head[N],to[N<<1],nxt[N<<1],cnt,tot,mx[N*60],xx[N],yy[N],zz[N];
int fa[N],top[N],son[N],siz[N],dep[N],root[N],ls[N*60],rs[N*60],ans[N],v[N];
inline void add(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs1(int x,int y)
{
int i; siz[x]=1; fa[x]=y; dep[x]=dep[y]+1;
for(i=head[x];i;i=nxt[i])
{
if(to[i]!=y)
{
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
}
void dfs2(int x,int t)
{
top[x]=t;
if(son[x]) dfs2(son[x],t);
int i;
for(i=head[x];i;i=nxt[i])
{
if(to[i]!=son[x]&&to[i]!=fa[x])
{
dfs2(to[i],to[i]);
}
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]]) swap(x,y);
y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
void pushup(int p)
{
if(t[ls[p]]>=t[rs[p]]) mx[p]=mx[ls[p]],t[p]=t[ls[p]];
else mx[p]=mx[rs[p]],t[p]=t[rs[p]];
}
int merge(int l,int r,int x,int y)
{
if(!x) return y;
if(!y) return x;
if(l==r)
{
t[x]+=t[y]; return x;
}
int mid=(l+r)>>1;
ls[x]=merge(l,mid,ls[x],ls[y]);
rs[x]=merge(mid+1,r,rs[x],rs[y]);
pushup(x);
return x;
}
void update(int l,int r,int x,int v,int &p)
{
if(!p) p=++tot;
if(l==r)
{
t[p]+=v; mx[p]=l; return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,v,ls[p]);
else update(mid+1,r,x,v,rs[p]);
pushup(p);
}
void dfs(int x)
{
int i;
for(i=head[x];i;i=nxt[i])
{
if(to[i]!=fa[x])
{
dfs(to[i]);
root[x]=merge(1,maxn,root[x],root[to[i]]);
}
}
if(t[root[x]]) ans[x]=v[mx[root[x]]];
}
int main()
{
scanf("%d%d",&n,&m);
int i,x,y,z;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y); add(x,y); add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&xx[i],&yy[i],&zz[i]);
v[i]=zz[i];
}
sort(v+1,v+m+1);
for(i=1;i<=m;i++)
{
zz[i]=lower_bound(v+1,v+m+1,zz[i])-v,x=xx[i],y=yy[i];
int l=lca(x,y);
update(1,maxn,zz[i],1,root[x]);
update(1,maxn,zz[i],1,root[y]);
update(1,maxn,zz[i],-1,root[l]);
if(fa[l]) update(1,maxn,zz[i],-1,root[fa[l]]);
}
dfs(1);
for(i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
}

小结:当时做这个题的时候感觉这辈子不会再碰了,但是学完主席树之后觉得就一傻逼题... ...

最新文章

  1. JVM-String比较-字节码分析
  2. CaptureManagerSDK
  3. 演义江湖PC端意见汇总
  4. 搭建linux下teamspeak3多人语音服务器
  5. Android Studio 导入第三方jar包
  6. BZOJ 1055 玩具取名
  7. c++链接数据库测试,中文有问题
  8. DDL中drop-alter table
  9. 学习makefile的一个工程示例
  10. 洛谷 P4409 [ZJOI2006] 皇帝的烦恼
  11. Sqring核心概念
  12. C语言Socket-模拟远程CMD(客户端向服务器发送命令,服务器执行该命令)
  13. mysql中,创建包含json数据类型的表?创建json表时候的注意事项?查询json字段中某个key的值?
  14. java常用类总结
  15. Sprint2的每日更新
  16. jQuery 属性操作attr().prop().text().html().val()
  17. 范浩强treap——可持久化
  18. C# 代码 获取桌面路径
  19. python date,datetime 和time的区别
  20. linux上mysql安装

热门文章

  1. poi读取word2003(.doc文档)中的表格
  2. poj 3498 March of the Penguins(拆点+枚举汇点 最大流)
  3. B2568 比特集合 树状数组
  4. 后台传list,前台接受
  5. Django之ORM的增删改查操作流程
  6. python 进程理论基础
  7. RRDtool入门详解
  8. js 全选选框与取消全选代码
  9. 存档:Telerik Test Studio的摸索笔记
  10. OpenCV: OpenCV人脸检测框可信度排序