bzoj 5457 城市

题目大意

给定一棵以$1$为根的$n$个节点的有根树。

每个节点有一个民族和该民族在当前节点的人数。

有$n$个询问，第$i$个询问是求以$i$为根的子树内，人数最多的民族是哪个，这个民族有多少人。

如果最多的民族有多个输出编号最小的。

数据范围

$1\le n\le 4\cdot 10^5$，$m\le n$，$1\le a_i\le m$，$0\le b_i\le 1000$。

题解

我们发现这个题满足一个性质，就是无修改、询问子树。

然后不难发现，这个题就是维护一个桶然后求编号最小的最大值，这东西显然可以合并啊。

好，无修改询问子树可合并，我们就考虑考虑$dsu\ on\ tree$。

想到$dsu\ on\ tree$这题就切掉了啊。

只需要维护一个每棵子树维护一个桶就好了。

代码

#include 
    
     #define N 400010 using namespace std;int to[N<<1],head[N],nxt[N<<1],tot;int st[N],a[N],b[N],size[N],son[N],ans_num[N],ans_id[N];int mx,id;char *p1,*p2,buf[100000];#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}void dfs1(int p,int fa){    size[p]=1;    for(int i=head[p];i;i=nxt[i]) if(to[i]!=fa)    {        dfs1(to[i],p);        size[p]+=size[to[i]];        if(size[to[i]]>size[son[p]]) son[p]=to[i];    }}void add(int p,int fa,int val){    st[a[p]]+=val*b[p];    if(st[a[p]]==mx&&a[p]
     
      mx) mx=st[a[p]],id=a[p];    for(int i=head[p];i;i=nxt[i]) if(to[i]!=fa) add(to[i],p,val);}void dfs2(int p,int fa,int opt){    for(int i=head[p];i;i=nxt[i]) if(to[i]!=fa&&to[i]!=son[p]) dfs2(to[i],p,0);    if(son[p]) dfs2(son[p],p,1);    for(int i=head[p];i;i=nxt[i]) if(to[i]!=fa&&to[i]!=son[p]) add(to[i],p,1);    st[a[p]]+=b[p];    if(st[a[p]]==mx&&a[p]
      
       mx) mx=st[a[p]],id=a[p];    ans_num[p]=mx,ans_id[p]=id;    if(!opt) add(p,fa,-1),mx=id=0;}int main(){    int n=rd(),m=rd();    for(int i=1;i