Description
有 n 座城市, m 个民族. 这些城市之间由 n-1 条道路连接形成了以城市 1 为根的有根树. 每个城市都是某一民族的聚居
地, Master 知道第 i 个城市的民族是 A_i, 人数是 B_i. 为了维护稳定, Master 需要知道某个区域内人数最多的民族
. 他向你提出 n 个询问, 其中第 i 个询问是: 求以 i 为根的子树内, 人数最多的民族有是哪个, 这个民族有多少人.
如果子树内人数最多的民族有多个, 输出其中编号最小的民族.
Input
共有 2*n 行.
第一行有两个整数 n, m.
接下来 n-1 行, 每行有两个整数 u, v, 表示一条连接 u 和 v 的道路.
接下来 n 行, 第 i 行有两个整数 A_i, B_i.
- n<=400000,m<=n,1<=A_i<=m,0<=B_i<=1000.
- Output
共有 n 行.
第 i 行两个整数 x, y, 分别表示以 i 为根的子树中人数最多的民族和它的人数.
- Sample Input
- 8 6
- 1 2
- 1 3
- 2 4
- 4 5
- 3 6
- 5 7
- 1 8
- 2 8
- 2 5
- 1 1
- 3 1
- 6 7
- 5 6
- 1 10
- 4 6
- Sample Output
- 2 13
- 1 10
- 5 6
- 1 10
- 1 10
- 5 6
- 1 10
- 4 6
思路: 从叶子开始往上不断的进行线段树合并. 用了一个 pair, 比较方便.
- #include<bits/stdc++.h>
- using namespace std;
- #define R register int
- #define rep(i,a,b) for(R i=a;i<=b;i++)
- #define Rep(i,a,b) for(R i=a;i>=b;i--)
- #define ms(i,a) memset(a,i,sizeof(a))
- #define gc() getchar()
- #define mid (l+r>>1)
- #define pii pair<int,int>
- #define fi first
- #define se second
- template<class T>void read(T &x){
- x=0; char c=0;
- while (!isdigit(c)) c=gc();
- while (isdigit(c)) x=x*10+(c^48),c=gc();
- }
- int const N=400000+3;
- struct Edge{
- int to,nt;
- }E[N<<1];
- int H[N],cnt,n,m,a[N],b[N],rt[N],lc[N*30],rc[N*30],sum;
- pii ans[N],mx[N*30];
- void add(int a,int b){
- E[cnt]=(Edge){b,H[a]}; H[a]=cnt++;
- }
- int merge(int x,int y,int l,int r){
- if(!x) return y;
- if(!y) return x;
- if(l==r) mx[x].fi+=mx[y].fi;
- else {
- lc[x]=merge(lc[x],lc[y],l,mid);
- rc[x]=merge(rc[x],rc[y],mid+1,r);
- mx[x]=max(mx[lc[x]],mx[rc[x]]);
- }
- return x;
- }
- void update(int &x,int l,int r,int a,int b){
- if(!x) x=++sum;
- if(l==r){
- mx[x].fi+=b;mx[x].se=-a;
- return ;
- }
- if(a<=mid) update(lc[x],l,mid,a,b);
- else update(rc[x],mid+1,r,a,b);
- mx[x]=max(mx[lc[x]],mx[rc[x]]);
- }
- void dfs(int x,int fa){
- for(R i=H[x];i!=-1;i=E[i].nt){
- int v=E[i].to;
- if(v==fa) continue;
- dfs(v,x);
- rt[x]=merge(rt[x],rt[v],1,m);
- }
- update(rt[x],1,m,a[x],b[x]);
- ans[x]=mx[rt[x]];
- }
- int main(){
- read(n); read(m);
- ms(-1,H);
- rep(i,1,n-1){
- int x,y;
- read(x); read(y);
- add(x,y); add(y,x);
- }
- rep(i,1,n) read(a[i]),read(b[i]);
- dfs(1,0);
- rep(i,1,n) printf("%d %d\n",-ans[i].se,ans[i].fi);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2990166.html