Relief grain
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)
Total Submission(s): 3246 Accepted Submission(s): 955
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5029
Problem Description
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.
Input
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
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
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
2
2
3
3
0
2
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
题意
题解
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200050
struct Edge{int from,to,s;}edges[N<<];
struct Query
{
int x,val,id;
bool operator <(const Query&b)const
{return x<b.x;}
}a[N<<];
struct Tree{int l,r,mx,wmx;}tr[N<<];
int n,m,num,ans[N];
int tot,last[N];
int cnt,fa[N],dp[N],size[N],son[N],rk[N],kth[N],top[N];
template<typename T>void read(T&x)
{
ll k=; char c=getchar();
x=;
while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
if (c==EOF)exit();
while(isdigit(c))x=x*+c-'',c=getchar();
x=k?-x:x;
}
void read_char(char &c)
{while(!isalpha(c=getchar())&&c!=EOF);}
void AddEdge(int x,int y)
{
edges[++tot]=Edge{x,y,last[x]};
last[x]=tot;
}
void dfs1(int x,int pre)
{
fa[x]=pre;
dp[x]=dp[pre]+;
size[x]=;
son[x]=;
for(int i=last[x];i;i=edges[i].s)
{
Edge &e=edges[i];
if (e.to==pre)continue;
dfs1(e.to,x);
size[x]+=size[e.to];
if (size[e.to]>size[son[x]])
son[x]=e.to;
}
}
void dfs2(int x,int y)
{
rk[x]=++cnt;
kth[cnt]=x;
top[x]=y;
if (son[x]==)return;
dfs2(son[x],y);
for(int i=last[x];i;i=edges[i].s)
{
Edge e=edges[i];
if (e.to==fa[x]||e.to==son[x])continue;
dfs2(e.to,e.to);
}
}
void push_up(Tree &c,Tree a,Tree b)
{
c.mx=max(a.mx,b.mx);
c.wmx=c.mx==a.mx?a.wmx:b.wmx;
}
void bt(int x,int l,int r)
{
tr[x]=Tree{l,r,,};
if (l==r){tr[x].wmx=l;return;}
int mid=(l+r)>>;
bt(x<<,l,mid);
bt(x<<|,mid+,r);
}
void update(int x,int p,int tt)
{
if (p<=tr[x].l&&tr[x].r<=p)
{
tr[x].mx+=tt;
tr[x].wmx=tr[x].l;
return;
}
int mid=(tr[x].l+tr[x].r)>>;
if (p<=mid)update(x<<,p,tt);
if (mid<p)update(x<<|,p,tt);
push_up(tr[x],tr[x<<],tr[x<<|]);
}
void change(int x,int y,int tt)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if (dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
a[++num]=Query{rk[fx],tt,};
a[++num]=Query{rk[x]+,tt,-};
x=fa[fx];fx=top[x];
}
if (dp[x]<dp[y])swap(x,y);
a[++num]=Query{rk[y],tt,};
a[++num]=Query{rk[x]+,tt,-};
}
void work()
{
read(n); read(m);
if (n==)exit();
for(int i=;i<=n-;i++)
{
int x,y;
read(x); read(y);
AddEdge(x,y);
AddEdge(y,x);
}
dfs1(,);
dfs2(,);
bt(,,);
for(int i=;i<=m;i++)
{
int x,y,tt;
read(x); read(y); read(tt);
change(x,y,tt);
}
sort(a+,a+num+);
for(int i=;i<=num-;i++)
{
int l=a[i].x;
update(,a[i].val,a[i].id);
while(a[i+].x==a[i].x)
//update(1,a[++i].val,a[i].id);
i++,update(,a[i].val,a[i].id); for(int j=l;j<a[i+].x;j++)
ans[kth[j]]=tr[].wmx;
}
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
}
void clear()
{
tot=; cnt=; num=;
memset(last,,sizeof(last));
memset(ans,,sizeof(ans));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
while()
{
clear();
work();
}
}