JDOJ 1985: [HN3.22]雨天的尾巴
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
5 3 1 2 3 1 3 4 5 4 2 3 3 1 5 2 3 3 3
Sample Output
2 3 3 2 2
HINT
【数据范围和约定】
对于20% 的数据，1<n,m <100
对于50% 的数据，1< n,m< 2000
对于100% 的数据，1<n,m<100000, 1<a, b, x, y< n, 1<z<109
题解：
和洛谷模板题稍有不同：
就是z变成了1e9，而洛谷的是1e5。
本来寻思需要离散化。
但是一想：动态开点啊，所以不用。
所以代码是一样的：
#include<cstdio>
#include<algorithm>
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=nc();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=nc();
return x*f;
}
const int maxn=1e5+10;
int n,m,maxx;
int tot,to[maxn<<1],nxt[maxn<<1],head[maxn];
int deep[maxn],size[maxn],fa[maxn],top[maxn],son[maxn],root[maxn];
int lson[maxn*60],rson[maxn*60],sum[maxn*60],wh[maxn*60],cnt;
//sum存最多救济粮个数，wh存最小编号的最多救济粮种类
int ans[maxn];
struct node
{
int x,y,z;
}q[maxn];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f)
{
deep[x]=deep[f]+1;
fa[x]=f;
size[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x);
size[x]+=size[y];
if(!son[x]||size[y]>size[son[x]])
son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
if(!son[x])
return;
dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x]||y==son[x])
continue;
dfs2(y,y);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}
void pushup(int pos)
{
if(sum[lson[pos]]>=sum[rson[pos]])
sum[pos]=sum[lson[pos]],wh[pos]=wh[lson[pos]];
else
sum[pos]=sum[rson[pos]],wh[pos]=wh[rson[pos]];
}
void update(int &pos,int l,int r,int x,int k)//将数x的个数+k
{
int mid=(l+r)>>1;
if(!pos)
pos=++cnt;
{
sum[pos]+=k;
wh[pos]=l;
return;
}
if(x<=mid)
update(lson[pos],l,mid,x,k);
else
update(rson[pos],mid+1,r,x,k);
pushup(pos);
}
void merge(int &x,int y,int l,int r)
{
int mid=(l+r)>>1;
if(!x||!y)
{
x=(!x?y:x);
return;
}
if(l==r)
{
sum[x]+=sum[y];
wh[x]=l;
return;
}
merge(lson[x],lson[y],l,mid);
merge(rson[x],rson[y],mid+1,r);
pushup(x);
}
void dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
dfs(y);
merge(root[x],root[y],1,maxx);
}
if(sum[root[x]])
ans[x]=wh[root[x]];
}
int main()
{
n=read();m=read();
for(int i=1;i<n;i++)
{
int x,y;
x=read();y=read();
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++)
{
q[i].x=read(),q[i].y=read(),q[i].z=read();
maxx=max(maxx,q[i].z);
}
for(int i=1;i<=m;i++)//树上的每一个节点有一棵权值线段树
{
int l=lca(q[i].x,q[i].y);
update(root[q[i].x],1,maxx,q[i].z,1);
update(root[q[i].y],1,maxx,q[i].z,1);
update(root[l],1,maxx,q[i].z,-1);
if(fa[l])
update(root[fa[l]],1,maxx,q[i].z,-1);
}
dfs(1);
for(int i=1;i<=n;i++)
printf("%d
",ans[i]);
return 0;
}