首页 > 代码库 > 树链剖分 [HDU 5029] Relief grain
树链剖分 [HDU 5029] Relief grain
Relief grain
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)
Total Submission(s): 1254 Accepted Submission(s): 299
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 41 21 1 11 2 22 2 22 2 15 31 23 13 45 32 3 31 5 23 3 30 0
Sample Output
1223302
Hint
For 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
2014 ACM/ICPC Asia Regional Guangzhou Online
这个题大概和5044一样的、也是利用前缀和的思想,比如1到5都加了3,那么就在查询1时加上3,查询6时减去3,用线段树来维护出现次数最多的。
最开始把100000写成n、找了好久的错。。。
#pragma comment(linker, "/STACK:1024000000,1024000000") //手动加栈、windows系统容易爆栈#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <vector>#include <map>#include <algorithm>using namespace std;#define INF 0x7ffffff#define ll __int64#define N 100010struct Edge{ int to,next;}edge[N<<1];int head[N],tot;int top[N];int fa[N];int deep[N];int size[N];int p[N];int fp[N];int son[N];int pos;int ans[N];vector<int>v1[N],v2[N];void init(){ tot=0; pos=1; memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son));}void add(int x,int y){ edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot++;}void dfs1(int now,int pre,int d){ deep[now]=d; fa[now]=pre; size[now]=1; for(int i=head[now];i!=-1;i=edge[i].next) { int next=edge[i].to; if(next!=pre) { dfs1(next,now,d+1); size[now]+=size[next]; if(son[now]==-1 || size[next]>size[son[now]]) { son[now]=next; } } }}void dfs2(int now,int tp){ top[now]=tp; p[now]=pos++; fp[p[now]]=now; if(son[now]==-1) return; dfs2(son[now],tp); for(int i=head[now];i!=-1;i=edge[i].next) { int next=edge[i].to; if(next!=son[now] && next!=fa[now]) { dfs2(next,next); } }}void change(int x,int y,int z){ int f1=top[x]; int f2 = top[y]; while(f1!=f2) { if(deep[f1]<deep[f2]) { swap(f1,f2); swap(x,y); } v1[p[f1]].push_back(z); v2[p[x]+1].push_back(z); x=fa[f1]; f1=top[x]; } if(deep[x]>deep[y]) swap(x,y); v1[p[x]].push_back(z); v2[p[y]+1].push_back(z);}/* 线段树 */int mx[N<<2];int id[N<<2];void pushup(int rt){ if(mx[rt<<1]<mx[rt<<1|1]) { mx[rt]=mx[rt<<1|1]; id[rt]=id[rt<<1|1]; } else { mx[rt]=mx[rt<<1]; id[rt]=id[rt<<1]; }}void build(int l,int r,int rt){ if(l==r) { id[rt]=l; mx[rt]=0; return; } int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt);}void update(int l,int r,int rt,int pos,int op){ if(l== pos && r == pos) { mx[rt]+=op; return; } int m=(l+r)>>1; if(pos<=m) update(l,m,rt<<1,pos,op); else update(m+1,r,rt<<1|1,pos,op); pushup(rt);}int main(){ int n,m,i,j; while(scanf("%d%d",&n,&m), n||m) { init(); for(i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs1(1,0,0); dfs2(1,1); for(i=1;i<=100000;i++) { v1[i].clear(); v2[i].clear(); } while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); change(a,b,c); } build(1,100000,1); for(i=1;i<=n;i++) { for(j=0;j<v1[i].size();j++) { update(1,100000,1,v1[i][j],1); } for(j=0;j<v2[i].size();j++) { update(1,100000,1,v2[i][j],-1); } if(!mx[1]) ans[fp[i]]=0; else ans[fp[i]]=id[1]; } for(i=1;i<=n;i++) { printf("%d\n",ans[i]); } } return 0;}
树链剖分 [HDU 5029] Relief grain
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。