hdu 5029 Relief grain(树链剖分好题)
拓拔迪
Relief grain
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)Total Submission(s): 295 Accepted Submission(s): 66
Problem Description
The soil is cracking up because of the drought and the rabbit kingdom is facing a serious famine. The RRC(Rabbit Red Cross) organizes the distribution of relief grain in the disaster area.
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
Input
The input consists of at most 25 test cases.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
Output
For each test case, output n integers. The i-th integer denotes the type that is distributed the most times in the i-th village. If there are multiple types which have the same times of distribution, output the minimal one. If there is no relief grain in a village, just output 0.
Sample Input
2 4 1 2 1 1 1 1 2 2 2 2 2 2 2 1 5 3 1 2 3 1 3 4 5 3 2 3 3 1 5 2 3 3 3 0 0
Sample Output
1 2 2 3 3 0 2HintFor the first test case, the relief grain in the 1st village is {1, 2}, and the relief grain in the 2nd village is {1, 2, 2}.
Source
Recommend
题意：
给你一颗节点数最多为1e5的树。然后是m(1e5)条操作
x y z。
就是把x到y路径上的所有点包括x,y图上x颜色。
最后要你输出，每个点被图的次数最多的颜色是那个。如果有多个输出z最小的那个z(1-1e5)。
思路：
先说下我比赛时的思路吧。虽然跟我下面要讲的方法比起来有点蠢。但是是自己想出来的。且能A掉这题。所以还是记录下吧。开始想这题时一头雾水。这题很明显是树链剖分加线段树。树链剖分那部分肯定不用怎么动了。关键就是线段树维护什么呀。维护什么颜色最多。由于操作图的颜色可能不规律。给每个结点开个数组明显不现实。纠结半天
注意到题目是先操作完再询问。所以可以考虑离线处理。先存下所有操作。然后按颜色排序。然后再用线段树维护。加的lazy是自己对应的区间col[rt]颜色被图了num[rt]次。比较麻烦的是如果一个区间如果有颜色了切和现在要标记的颜色不一样怎么办。最蠢的办法就是先把现在的标记PushDown下去然后再标记。但是这样到一定时候跟暴力没什么区别。注意到我们对颜色排序了。所以可以知道颜色标记在线段树里是一层一层分布的。也就是可以确定的是两个不同颜色标记之间的树只可能一种颜色。所以我们PushDown的时候有些标记是没必要PushDown的。比如现在在图5颜色。而现在要下传的标记是3颜色。而子树却是2颜色。如果3颜色标记数目小于2颜色标记的话就不用下传了。因为所有3颜色肯定全部集中在3这个标记了(因为颜色是分层的。3颜色标记已经全部被5这个颜色标记推到2这里了)。所以3一定成不了答案。由于比赛时代码写残了。到最后还是wa。比赛后各种找bug也没找到。于是用admin账号copy了几个AC代码对拍。结果发现AC代码居然有好几个是错的。。(因为我也只找了几个)可见数据也是蛮水的。。。
后来我程序还是成功debug了。用时2s多一点。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define lson L,mid,ls
#define rson mid+1,R,rs
int sz[maxn],dep[maxn],fa[maxn],son[maxn],id[maxn],top[maxn],rd[maxn];
int col[maxn<<2],num[maxn<<2],cnum[maxn],ccol[maxn],ans[maxn],cnt,ptr,ccl;
struct node
{
int v;
node *next;
} ed[maxn<<1],*head[maxn];
struct qnode
{
int u,v,cc;
} qq[maxn];
bool cmp(qnode a,qnode b)
{
return a.cc<b.cc;
}
void adde(int u,int v)
{
ed[cnt].v=v;
ed[cnt].next=head[u];
head[u]=&ed[cnt++];
}
void build(int L,int R,int rt)
{
col[rt]=num[rt]=0;
if(L==R)
{
ccol[L]=cnum[L]=0;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void PushDown(int L,int R,int rt)
{
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(mid==L)
{
if(col[ls]==col[rt]||col[ls]==0)
{
col[ls]=col[rt];
num[ls]+=num[rt];
}
else
{
if(ccol[L]!=col[rt])
ccol[L]=col[rt],cnum[L]=num[rt];
else
cnum[L]+=num[rt];
if(cnum[L]>num[ls])
{
num[ls]=cnum[L];
col[ls]=col[rt];
}
}
}
else if(col[ls]==col[rt]||col[ls]==0)
{
col[ls]=col[rt];
num[ls]+=num[rt];
}
else
{
if(num[ls]<num[rt]||ccl==col[rt])
{
PushDown(L,mid,ls);
col[ls]=col[rt];
num[ls]=num[rt];
}
}
if(mid+1==R)
{
if(col[rs]==col[rt]||col[rs]==0)
{
col[rs]=col[rt];
num[rs]+=num[rt];
}
else
{
if(ccol[R]!=col[rt])
ccol[R]=col[rt],cnum[R]=num[rt];
else
cnum[R]+=num[rt];
if(cnum[R]>num[rs])
{
num[rs]=cnum[R];
col[rs]=col[rt];
}
}
}
else if(col[rs]==col[rt]||col[rs]==0)
{
col[rs]=col[rt];
num[rs]+=num[rt];
}
else
{
if(num[rs]<num[rt]||ccl==col[rt])
{
PushDown(mid+1,R,rs);
col[rs]=col[rt];
num[rs]=num[rt];
}
}
//printf("push %d->%d col %d num %d\n",L,mid,col[ls],num[ls]);
//printf("push %d->%d col %d num %d\n",mid+1,R,col[rs],num[rs]);
col[rt]=num[rt]=0;
}
void update(int L,int R,int rt,int l,int r,int c)
{
if(l<=L&&R<=r)
{
if(c==col[rt]||col[rt]==0)
{
col[rt]=c;
num[rt]++;
//printf("X %d->%d col %d num %d\n",L,R,col[rt],num[rt]);
return;
}
if(L!=R)
{
PushDown(L,R,rt);
col[rt]=c;
num[rt]=1;
}
else
{
if(ccol[L]!=c)
ccol[L]=c,cnum[L]=1;
else
cnum[L]++;
if(cnum[L]>num[rt])
{
num[rt]=cnum[L];
col[rt]=c;
}
}
//printf("X %d->%d col %d num %d\n",L,R,col[rt],num[rt]);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(col[rt]!=0)
PushDown(L,R,rt);
if(l<=mid)
update(lson,l,r,c);
if(r>mid)
update(rson,l,r,c);
//printf("X %d->%d col %d num %d\n",L,R,col[rt],num[rt]);
}
void qu(int L,int R,int rt)
{
if(L==R)
{
if(cnum[L]>num[rt])
col[rt]=ccol[L];
ans[rd[L]]=col[rt];
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(col[rt]!=0)
PushDown(L,R,rt);
qu(lson);
qu(rson);
}
void dfs(int u)
{
int v,ms=0;
sz[u]=1,son[u]=-1;
for(node *p=head[u];p!=NULL;p=p->next)
{
v=p->v;
if(v==fa[u])
continue;
dep[v]=dep[u]+1;
fa[v]=u;
dfs(v);
if(sz[v]>ms)
ms=sz[v],son[u]=v;
sz[u]+=sz[v];
}
}
void getid(int u,int ft)
{
id[u]=++ptr,top[u]=ft,rd[ptr]=u;
if(son[u]!=-1)
getid(son[u],top[u]);
for(node *p=head[u];p!=NULL;p=p->next)
{
if(p->v==son[u]||p->v==fa[u])
continue;
getid(p->v,p->v);
}
}
void init(int rt)
{
fa[rt]=-1;
dep[rt]=ptr=0;
dfs(rt);
getid(rt,rt);
}
void uppath(int u,int v,int d)
{
//printf("u %d v %d c %d\n",u,v,d);
int f1=top[u],f2=top[v];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
swap(f1,f2),swap(u,v);
//printf("%d->%d\n",id[f1],id[u]);
update(1,ptr,1,id[f1],id[u],d);
u=fa[f1],f1=top[u];
}
if(dep[u]>dep[v])
swap(u,v);
//printf("%d->%d\n",id[u],id[v]);
update(1,ptr,1,id[u],id[v],d);
}
int main()
{
int n,m,i,rt,u,v;
//freopen("in.txt","r",stdin);
//freopen("out1.txt","w",stdout);
while(scanf("%d%d",&n,&m),n||m)
{
cnt=0;
memset(head,0,sizeof head);
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
rt=(n+1)/2;
init(rt);
build(1,ptr,1);
for(i=0;i<m;i++)
scanf("%d%d%d",&qq[i].u,&qq[i].v,&qq[i].cc);
sort(qq,qq+m,cmp);
//for(i=1;i<=n;i++)
//printf("i %d id %d\n",i,id[i]);
for(i=0;i<m;i++)
{
ccl=qq[i].cc;
uppath(qq[i].u,qq[i].v,qq[i].cc);
}
ccl=-1;
qu(1,ptr,1);
for(i=1;i<=n;i++)
printf("%d\n",ans[i]);
}
return 0;
}方法就是打标记。线段树维护的是颜色。也就是维护的是[a,b]就是维护a颜色到b颜色某种颜色出现的最多次数。
假设我们处理的是序列而不是树吧。比如我们要把区间[x,y]图成a颜色.那么我们就在x出加个标记a。在y+1就标记-a。
多个标记用邻接表连起来就行了。然后从序列的最左端处理到最右端先把所有标记更新到线段树里。a则a颜色+1。
-a则在线段树将a颜色-1.然后再询问线段树里出现最多的次数就是序列该位置的次数最多的颜色了。相当于递推的思想吧。知道了x位置的颜色线段树.x+1位置的颜色线段树无非是多了一些颜色或者少了某些颜色。多了减掉。少了的加上就是自己这个位置上的了。这样做之所以高效的原因是标记的是区间的端点而不是区间类的每一个元素。总的时间复杂度m*log(n)*log(c)。m为询问数。n为结点数。c为颜色种数。应该是极限了吧。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define lson L,mid,ls
#define rson mid+1,R,rs
int sz[maxn],dep[maxn],fa[maxn],son[maxn],id[maxn],top[maxn];
int mv[maxn<<2],ans[maxn],leaf[maxn],cnt,ptr,col;
struct node
{
int v;
node *next;
} ed[(maxn<<1)+40*maxn],*head[maxn],*oh[maxn];
void adde(node *h[],int u,int v)
{
ed[cnt].v=v;
ed[cnt].next=h[u];
h[u]=&ed[cnt++];
}
void build(int L,int R,int rt)
{
mv[rt]=0;
if(L==R)
{
leaf[L]=rt;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void update(int rt,int c)
{
int ls,rs;
mv[rt]+=c;
while(rt>1)
{
rt>>=1;
ls=rt<<1,rs=ls|1;
mv[rt]=max(mv[ls],mv[rs]);
}
}
int qu(int L,int R,int rt)
{
int ls,rs,mid;
if(mv[rt]==0)
return 0;
while(L<R)
{
ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(mv[rs]>mv[ls])
L=mid+1,rt=rs;
else
R=mid,rt=ls;
}
return L;
}
void dfs(int u)
{
int v,ms=0;
sz[u]=1,son[u]=-1;
for(node *p=head[u];p!=NULL;p=p->next)
{
v=p->v;
if(v==fa[u])
continue;
dep[v]=dep[u]+1;
fa[v]=u;
dfs(v);
if(sz[v]>ms)
ms=sz[v],son[u]=v;
sz[u]+=sz[v];
}
}
void getid(int u,int ft)
{
id[u]=++ptr,top[u]=ft;
if(son[u]!=-1)
getid(son[u],top[u]);
for(node *p=head[u];p!=NULL;p=p->next)
{
if(p->v==son[u]||p->v==fa[u])
continue;
getid(p->v,p->v);
}
}
void init(int rt)
{
fa[rt]=-1;
dep[rt]=ptr=0;
dfs(rt);
getid(rt,rt);
}
void uppath(int u,int v,int d)
{
int f1=top[u],f2=top[v];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
swap(f1,f2),swap(u,v);
adde(oh,id[f1],d);
adde(oh,id[u]+1,-d);
u=fa[f1],f1=top[u];
}
if(dep[u]>dep[v])
swap(u,v);
adde(oh,id[u],d);
adde(oh,id[v]+1,-d);
}
int main()
{
int n,m,i,rt,u,v,z;
col=100005;
while(scanf("%d%d",&n,&m),n||m)
{
cnt=0;
for(i=1;i<=n;i++)
head[i]=oh[i]=NULL;
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
adde(head,u,v);
adde(head,v,u);
}
rt=(n+1)/2;
init(rt);
build(1,col,1);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&z);
uppath(u,v,z);
}
for(i=1;i<=n;i++)
{
for(node *p=oh[i];p!=NULL;p=p->next)
if(p->v>0)
update(leaf[p->v],1);
else
update(leaf[-p->v],-1);
ans[i]=qu(1,col,1);
}
for(i=1;i<=n;i++)
printf("%d\n",ans[id[i]]);
}
return 0;
}
/*
5 10
3 4
5 2
5 1
5 4
5 5 17
1 4 18
4 4 13
3 3 7
4 5 5
3 2 12
3 1 13
3 5 10
1 2 12
4 3 5
5 5
1 4
3 4
4 5
4 2
5 2 2
4 3 8
5 4 15
4 1 8
3 4 2
0 0
*/
类似资料：