树上启发式合并两道 codeforces

600E Lomsat gelral

题意: 给你一个有根树，每个节点都有一种颜色，询问某个节点的子树中颜色最多的编号和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
    int v,nxt;
}edge[N*2];
int tot;
ll maxx,sum,ans[N];
int col[N],cnt[N],sz[N],big[N],head[N];
 
void add(int u,int v)
{
    edge[tot].v=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
 
void dfsbig(int u,int fa)
{
    sz[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa)
            continue;
        dfsbig(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[big[u]]||!big[u])
            big[u]=v;
    }
}
 
void update(int u,int fa,int k)
{
    cnt[col[u]]+=k;
    if(k>0&&cnt[col[u]]>=maxx)
    {
        if(cnt[col[u]]>maxx)
            sum=0,maxx=cnt[col[u]];
        sum+=col[u];
    }
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa)
            continue;
        update(v,u,k);
    }
}
 
void dfs(int u,int fa)
{
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa||v==big[u])
            continue;
        dfs(v,u);
        update(v,u,-1);
        maxx=0;sum=0;
    }
    if(big[u])
        dfs(big[u],u);
     for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa||v==big[u])
            continue;
        update(v,u,1);
    }
    cnt[col[u]]++;
    if(cnt[col[u]]>=maxx)
    {
        if(cnt[col[u]]>maxx)
            sum=0,maxx=cnt[col[u]];
        sum+=col[u];
    }
    //cout<<u<<' '<<sum<<endl;
    ans[u]=sum;
}
 
int main()
{
    memset(head,-1,sizeof head);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&col[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfsbig(1,0);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    puts("");
    return 0;
}
           

570D Tree Requests

题意: 给你一个有根树，每个节点都有一个小写字母，询问某个节点的子树中深度为h的所有子节点是否能构成回文串，空串也算回文串

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct node
{
    int v,nxt;
}edge[N*2];
int head[N],sz[N],big[N],depth[N],ans[N],ch[N];
int cnt[N][26];
int tot;
char s[N];
vector<pair<int,int> >qu[N];
void add(int u,int v)
{
    edge[tot].v=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
 
void dfs_big(int u,int fa)
{
    sz[u]=1;
    depth[u]=depth[fa]+1;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa)
            continue;
        dfs_big(v,u);
        sz[u]+=sz[v];
        if(!big[u]||sz[big[u]]<sz[v])
            big[u]=v;
    }
}
 
void update(int u,int fa,int k)
{
    cnt[depth[u]][ch[u]]+=k;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa)
            continue;
        update(v,u,k);
    }
}
 
void dfs(int u,int fa)
{
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa||v==big[u])
            continue;
        dfs(v,u);
        update(v,u,-1);
    }
    if(big[u])
       dfs(big[u],u);
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa||v==big[u])
            continue;
        update(v,u,1);
    }
    cnt[depth[u]][ch[u]]++;
    for (int i=0,siz=qu[u].size(); i<siz; ++i)
    {
        int flag = 0, id = qu[u][i].second, h = qu[u][i].first;
        for (int j=0; j<26; ++j) if (cnt[h][j] & 1) flag ++;
	ans[id] = (flag <= 1);
    }
}
 
int main()
{
    memset(head,-1,sizeof head);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
    {
        int u;
        scanf("%d",&u);
        add(u,i);
        add(i,u);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        ch[i]=s[i]-'a';
    for(int i=1;i<=m;i++)
    {
        int h,root;
        scanf("%d%d",&root,&h);
        qu[root].push_back(make_pair(h,i));
    }
    dfs_big(1,0);
    //for(int i=1;i<=n;i++)
	//cout<<big[i]<<endl;
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        if(ans[i])
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}