[BZOJ5457]城市


题目链接:[BZOJ5457]城市


Description
n座城市,m个民族。这些城市之间由n-1条道路连接形成了以城市1为根的有根树。每个城市都是某一民族的聚居地,Master知道第i个城市的民族是A_i,人数是B_i。为了维护稳定,Master需要知道某个区域内人数最多的民族。他向你提出n个询问,其中第i个询问是:求以i为根的子树内,人数最多的民族有是哪个,这个民族有多少人。如果子树内人数最多的民族有多个,输出其中编号最小的民族。


Input
共有2\times n行。
第一行有两个整数n,m
接下来n-1行,每行有两个整数u,v,表示一条连接uv的道路。
接下来n行,第i行有两个整数A_i,B_i
n\leqslant400000,m\leqslant n,1\leqslant A_i\leqslant m,0\leqslant B_i\leqslant 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


Solution
学dsu on tree写的板子题,据说叫做树上并查集??


Code

/**************************************************************
    Problem: 5457
    User: TaK-Vin(not username)
    Language: C++
    Result: Accepted
    Time:1932 ms
    Memory:21744 kb
****************************************************************/

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define Judge
#define Online
#define maxn 401000
#define rg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen("bzoj5457.in","r+");
FILE*out=fopen("bzoj5457.out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
struct node{
    int id,val; node():id(0),val(0){}
    node(int _id,int _val):id(_id),val(_val){}
    inline void ins(){read(id),read(val);}
    inline void out(){wt(id,' '),wt(val,'\n');}
}v[maxn],ans[maxn];
int fir[maxn],to[maxn<<1],nxt[maxn<<1],cnt,sz[maxn];
int n,m,num[maxn];
inline void ins(int x,int y){
    nxt[++cnt]=fir[x],fir[x]=cnt,to[cnt]=y;
    nxt[++cnt]=fir[y],fir[y]=cnt,to[cnt]=x;
}
inline void dfs1(int x,int fa){
    sz[x]=1;//get size
    for (rg int i=fir[x]; i; i=nxt[i]){
        if (to[i]==fa) continue;
        dfs1(to[i],x);sz[x]+=sz[to[i]];
    }
}
inline void add(int x,int y,int d,int opt){
    if (!opt) return void(num[x]-=y);num[x]+=y;
    if (num[x]>ans[d].val||(num[x]==ans[d].val&&x<ans[d].id))
        ans[d].val=num[x],ans[d].id=x;
}
inline void update(int x,int fa,int d,int opt){
    add(v[x].id,v[x].val,d,opt); for (rg int i=fir[x]; i; i=nxt[i])
        (to[i]==fa)?void():update(to[i],x,d,opt);
}
inline void dfs2(int x,int fa){
    //Find heavy son at first
    int s=0;
    for (rg int i=fir[x]; i; i=nxt[i])
        if (to[i]!=fa&&sz[to[i]]>sz[s])s=to[i];
    //Then add light sons
    for (rg int i=fir[x]; i; i=nxt[i])
        if (to[i]==fa||to[i]==s) continue;
        else dfs2(to[i],x),update(to[i],x,x,0);
    //Arfter that update the heavy son
    if (s) dfs2(s,x),ans[x].val=ans[s].val,ans[x].id=ans[s].id;
    add(v[x].id,v[x].val,x,1);
    //Finally update the light son
    for (rg int i=fir[x]; i; i=nxt[i])
        if (to[i]==fa||to[i]==s) continue; else update(to[i],x,x,1);
}
int main(int argv,char*argc[]){
    read(n),read(m);
    for (rg int x,y,i=1; i<n; ++i) read(x),read(y),ins(x,y);
    for (rg int i=1; i<=n; ++i) v[i].ins();
    dfs1(1,0),dfs2(1,0);for (rg int i=1; i<=n; ++i) ans[i].out();
    return 0;
}


点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s