T1

题目

一片森林，每次询问一个点与多少个点拥有共同的K级祖先

友好链接

https://www.luogu.com.cn/problem/CF208E

https://www.luogu.com.cn/blog/defKaeru/solution-cf208e

题解

我们首先考虑在一棵树上处理的情况，把问题转换一下，其实让你求的就是以某个节点为根的子树中的深度为k的节点个数

因此我们可以用倍增法先求出每一个节点的K级祖先，然后再在第k级祖先上处理维护答案就行了。

code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf= 0x3f3f3f3f;
const int N = 5e5+9;
int n,m;
int dep[N],sz[N],hson[N];
int cnt[N],ans[N],color[N];
int vis[N];
int f[N][26];
vector<int>g[N];
vector<pii>Q[N];


template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

void dfs_tree(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]= 1;
    f[x][0]=fa;
    rep(i,1,20) f[x][i]=f[f[x][i-1]][i-1];
    for (auto j:g[x])
    {
        if(j==fa)continue;
        dfs_tree(j,x);
        sz[x]+=sz[j];
        if(sz[hson[x]]<sz[j])hson[x]=j;
    }
}

void calc (int u,int f,int k)
{
    /// 统计整个子树的信息
    cnt[dep[u]]+=k;
    for(auto v:g[u])
    {
        if(v!=f&&!vis[v])///不反祖且未被访问
        {
            calc(v,u,k);
        }
    }
}

void dfs_dsu(int u,int f,int keep)
{
    for(auto v:g[u])
    {
        if(v!=hson[u]&&v!=f)
            {
                dfs_dsu(v,u,0);
            }
    }
        /// 递归处理子树问题

    if(hson[u])dfs_dsu(hson[u],u,1),vis[hson[u]]=1;
    calc(u,f,1);///统计非重子树的信息
    for(int i= 0;i < Q[u].size() ; i++)
    {
        int id = Q[u][i].first;  ///询问编号
        int d = Q[u][i].second;  ///询问深度
        ans[id]=cnt[d]-1;
    }
    if(hson[u])vis[hson[u]]=0;
    if(keep==0)calc(u,f,-1);
}

void pre()
{
    for (int k = 1;k <= 26 ; k ++)
    {
         for (int i = 1; i <= n ; i++) f[i][k]=f[f[i][k-1]][k-1];
    }
}


int getfa(int x,int lev)
{
    for(int i=20;~i;i--)
    {
        if(lev&(1<<i))x=f[x][i];
    }
    return x;
}

int main()
{
    read(n);
    rep(i,1,n)
    {
        int x; read(x);
        if(x) g[x].pb(i),g[i].pb(x);
    }

    read(m);
    rep(i,1,n)if(!dep[i])dfs_tree(i,0);

    rep(i,1,m)
    {
        int v,p;
        read(v); read(p);
        int fax= getfa(v,p); ///获取v的p级祖先
        Q[fax].pb({i,dep[v]});
    }
    rep(i,1,n)if(dep[i]==1)dfs_dsu(i,0,0);
    rep(i,1,m)printf("%d\n",ans[i]);
    return 0;
}

T2

题目

给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，

每个点的深度定义为该节点到1号节点路径上的点数.

每次询问 a,b.查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.

友好链接

https://www.luogu.com.cn/problem/CF570D

题解

T1的cnt基础上再加上一维颜色

重排之后构成回文串的条件是：每个字母出现次数都为偶数或者只有一个字母出现次数为奇数。

因此我们可以直接维护cnt数组来统计子树中在某个深度上每个字符出现次数，然后再检查是否符合条件就行了。

至于查询操作，我们可以离线处理，然后把它挂在节点上，每当统计到该节点时，更新答案就行了。

code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf= 0x3f3f3f3f;
const int N = 5e5+9;
int n,m;
int dep[N],sz[N],hson[N];
int cnt[N][30],ans[N],color[N];
int vis[N];
vector<int>g[N];
vector<pii>Q[N];


template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

void dfs_tree(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]= 1;
    for (auto j:g[x])
    {
        if(j==fa)continue;
        dfs_tree(j,x);
        sz[x]+=sz[j];
        if(sz[hson[x]]<sz[j])hson[x]=j;
    }
}

void calc (int u,int f,int k)
{
    /// 统计整个子树的信息
    cnt[dep[u]][color[u]]+=k;
    for(auto v:g[u])
    {
        if(v!=f&&!vis[v])///不反祖且未被访问
        {
            calc(v,u,k);
        }
    }
}

void dfs_dsu(int u,int f,int keep)
{
    for(auto v:g[u])
    {
        if(v!=hson[u]&&v!=f)
            {
                dfs_dsu(v,u,0);
            }
    }
        /// 递归处理子树问题

    if(hson[u])dfs_dsu(hson[u],u,1),vis[hson[u]]=1;
    calc(u,f,1);///统计非重子树的信息
    for(int i= 0;i < Q[u].size() ; i++)
    {
        int id = Q[u][i].first;  ///询问编号
        int d = Q[u][i].second;  ///询问深度
        int num = 0;

        for(int j = 1;j<= 26;j++)
            if(cnt[d][j]&1) num++;

        ans[id]=num>1?0:1;
    }
    if(hson[u])vis[hson[u]]=0;
    if(keep==0)calc(u,f,-1);
}

int main()
{
    read(n); read(m);
    rep(i,2,n)
    {
        int x; read(x);
        g[x].pb(i); g[i].pb(x);
    }
    char s[N];
    scanf("%s",s+1);
    int len = strlen(s+1);
    rep(i,1,len)color[i]=s[i]-'a'+1;
    dfs_tree(1,0);
    rep(i,1,m)
    {
        int x,y;
        read(x); read(y);
        Q[x].pb({i,y});
    }
    dfs_dsu(1,0,1);
    rep(i,1,m)
    {
        if(ans[i])puts("Yes");
        else puts("No");
    }
    return 0;
}

T3

题目

给定一棵由 n 个节点组成的树。

树的节点编号为 1∼n，其中 1 号节点为树的根节点。

每个节点上都标有某种颜色。

第 i 个节点上的颜色为 ci。

如果在以节点 v 为根节点的子树中，没有任何颜色的出现次数超过颜色 c 的出现次数，那么我们称颜色 c 为该子树的主要颜色。

一些子树的主要颜色可能不止一种。

以节点 v 为根节点的子树由节点 v 以及到达根节点的路径中包含节点 v 的其它所有节点共同组成。

对于每个节点 v(1≤v≤n)，请你求出以该节点为根节点的子树的所有主要颜色之和。

友好链接

https://www.luogu.com.cn/problem/CF600E

题解

• 注意统计答案的时候不用遍历cnt数组，可以在加减档过程中维护
• 注意开ll
• 注意不要忘记开重链剖分

code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf= 0x3f3f3f3f;
const int N = 5e5+9;
int n,m;
int dep[N],sz[N],hson[N];
ll cnt[N],ans[N];
int col[N];
int vis[N];
int f[N][26];
vector<int>g[N];
vector<pii>Q[N];
ll sum,mx;

template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

void dfs_tree(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]= 1;
    for (auto j:g[x])
    {
        if(j==fa)continue;
        dfs_tree(j,x);
        sz[x]+=sz[j];
        if(sz[hson[x]]<sz[j])hson[x]=j;
    }
}

void calc (int u,int f,int k)
{
    /// 统计整个子树的信息
    cnt[col[u]]+=k;

    if(cnt[col[u]]>mx)sum=col[u],mx=cnt[col[u]];
    else if(cnt[col[u]]==mx)sum+=col[u];


    for(auto v:g[u])
    {
        if(v!=f&&!vis[v])///不反祖且未被访问
        {
            calc(v,u,k);
        }
    }
}

void dfs_dsu(int u,int f,int keep)
{
    for(auto v:g[u])
    {
        if(v!=hson[u]&&v!=f)
            {
                dfs_dsu(v,u,0);
            }
    }
        /// 递归处理子树问题

    if(hson[u])dfs_dsu(hson[u],u,1),vis[hson[u]]=1;
    calc(u,f,1);///统计非重子树的信息
    ans[u]=sum;
    if(hson[u])vis[hson[u]]=0;
    if(keep==0)calc(u,f,-1),mx=sum= 0;
}


int main()
{
    read(n);

    rep(i,1,n)read(col[i]);

    rep(i,1,n-1)
    {
        int v,p;
        read(v); read(p);
        g[v].pb(p); g[p].pb(v);
    }
    dfs_tree(1,0);
    dfs_dsu(1,0,0);
    rep(i,1,n)printf("%lld ",ans[i]);
    return 0;
}

T4

题目

给出一棵 n 个结点的树，每个结点有一个颜色 c i 。 询问 q 次，每次询问以 v 结点为根的子树中，出现次数 ≥k 的颜色有多少种。树的根节点是1.

友好链接

https://www.luogu.com.cn/problem/CF375D

题解

维护一个后缀和，我们结合calc函数看一下框架

考虑到出现次数k最大不超过点数，开一个桶是可行的

num[x] 表示出现次数大于等于 k 的次数

考虑到增加的时候是一个一个加的，删除的时候，每删除一个也是只对删除的当前k造成了影响，只要处理这一位就好了，不用管前面的或者后面的

void calc (int u,int f,int k)
{
    int pos = col[u];
    /// num[x] 表示出现次数大于等于k的计数
    if(k==-1) num[cnt[pos]]+=k;

    cnt[pos]+=k;
    if(k==1) num[cnt[pos]]+=k;

    for (auto v:g[u])
    {
        if(v!=f&&!vis[v])calc(v,u,k);
    }
}

code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf= 0x3f3f3f3f;
const int N = 5e5+9;
int n,m;
int dep[N],sz[N],hson[N];
int cnt[N],ans[N];
int col[N];
int vis[N];
int num[N];
vector<int>g[N];
vector<pii>Q[N];
int colmax;

template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

void dfs_tree(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]= 1;
    for (auto j:g[x])
    {
        if(j==fa)continue;
        dfs_tree(j,x);
        sz[x]+=sz[j];
        if(sz[hson[x]]<sz[j])hson[x]=j;
    }
}

void calc (int u,int f,int k)
{
    int pos = col[u];
    /// num[x] 表示出现次数大于等于k的计数
    if(k==-1) num[cnt[pos]]+=k;

    cnt[pos]+=k;
    if(k==1) num[cnt[pos]]+=k;

    for (auto v:g[u])
    {
        if(v!=f&&!vis[v])calc(v,u,k);
    }
}

void dfs_dsu(int u,int f,int keep)
{
    for(auto v:g[u])
    {
        if(v!=hson[u]&&v!=f)
            {
                dfs_dsu(v,u,0);
            }
    }
        /// 递归处理子树问题

    if(hson[u])dfs_dsu(hson[u],u,1),vis[hson[u]]=1;
    calc(u,f,1);///统计非重子树的信息
    for (int i= 0;i<Q[u].size();i++)
    {
        ll sum =0;
        int id = Q[u][i].first;
        int d = Q[u][i].second;
        ans[id]=num[d];
    }

    if(hson[u])vis[hson[u]]=0;
    if(keep==0)calc(u,f,-1);
}
int main()
{
    read(n);read(m);
    rep(i,1,n)read(col[i]),colmax=max(colmax,col[i]);
    rep(i,1,n-1)
    {
        int a,b;
        read(a); read(b);
        g[b].pb(a);
        g[a].pb(b);
    }

    dfs_tree(1,0);
    rep(i,1,m)
    {
        int v,p;
        read(v);read(p);
        Q[v].pb({i,p});
    }

    dfs_dsu(1,0,1);
    rep(i,1,m)printf("%d\n",ans[i]);

    return 0;
}

T5

题目

给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。

对于每个点，求一个最小的 k，使得 d(u,k) 最大。

友好链接

https://www.luogu.com.cn/problem/CF1009F

题解

注意答案统计方式，在注销非重儿子的时候，可以认为开始新的问题，答案的状态可设置为初始状态

void calc(int u,int f,int k)
{
    cnt[dep[u]]+=k;
    if(k>0&&cnt[dep[u]]>=maxcnt)
    {
        if(cnt[dep[u]]>maxcnt)maxcnt=cnt[dep[u]],mindep=dep[u];
        else if(cnt[dep[u]]==maxcnt)mindep=min(mindep,dep[u]);
    }

    for(auto v:g[u])
    {
        if(v!=f&&!vis[v])calc(v,u,k);
    }
}

code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf= 0x3f3f3f3f;
const int N = 1e6+9;
int n,m;
int dep[N],sz[N],hson[N];
int cnt[N],ans[N];
int vis[N];
vector<int>g[N];
vector<pii>Q[N];
int mindep,maxcnt;

template <typename T> void inline read(T &x)
{
    x= 0 ; bool f= 0; char ch  = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')f= 1; ch = getchar();}
    while (ch <='9' && ch >= '0') {x= (x<<1)+ (x<<3) + ch - '0'; ch = getchar();}
    if(f)x*=-1;
}

void dfs_tree(int u,int f)
{
    sz[u]= 1;
    dep[u]=dep[f]+1;
    for(auto v:g[u])
    {
        if(v==f)continue;
        dfs_tree(v,u);
        sz[u]+=sz[v];
        if(sz[hson[u]]<sz[v])hson[u]=v;
    }
}

void calc(int u,int f,int k)
{
    cnt[dep[u]]+=k;
    if(k>0&&cnt[dep[u]]>=maxcnt)
    {
        if(cnt[dep[u]]>maxcnt)maxcnt=cnt[dep[u]],mindep=dep[u];
        else if(cnt[dep[u]]==maxcnt)mindep=min(mindep,dep[u]);
    }

    for(auto v:g[u])
    {
        if(v!=f&&!vis[v])calc(v,u,k);
    }
}

void dfs_dsu(int u,int f,int keep)
{
    for(auto v:g[u])
    {
        if(v!=hson[u]&&v!=f) dfs_dsu(v,u,0);
    }
    if(hson[u])dfs_dsu(hson[u],u,1),vis[hson[u]]= 1;
    calc(u,f,1);
    ans[u]=mindep-dep[u];
    if(hson[u])vis[hson[u]]=0;
    if(keep==0)calc(u,f,-1),mindep=inf,maxcnt=0;
}

int main()
{
    read(n);
    rep(i,1,n-1)
    {
        int a,b;
        read(a); read(b);
        g[a].pb(b); g[b].pb(a);
    }
    dfs_tree(1,0);
    dfs_dsu(1,0,1);
    rep(i,1,n)printf("%d\n",ans[i]);
    return 0;
}

T6

题目

友好链接

题解

code