dsu on tree 练习题

参考链接：https://blog.csdn.net/qq_43472263/article/details/104150940

U41492 树上数颜色 https://www.luogu.com.cn/problem/U41492

求子树的颜色数有多少种

/*
U41492 树上数颜色
计算v的子树中颜色有多少种
*/
#include
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define pb push_back
using namespace std;
const int N = 100010;
int sz[N],son[N];//字树大小、重儿子编号
int col[N],ans[N],now,cnt[N];//i点的颜色，第i个问题的答案，当前颜色数，i颜色的数量
vector<int>G[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){ //暴力更新答案，op = 1为增加答案，op = -1为减少答案
    cnt[col[u]] += op;
    if(op == 1 && cnt[col[u]] == 1)now++;
    if(op == -1 && cnt[col[u]] == 0)now--;
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    cnt[col[u]]++;if(cnt[col[u]] == 1)now++;//加上当前点的贡献
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)solve(v,u,1);//添加贡献
    }
    ans[u] = now; //更新答案
    if(op == 1)solve(u,f,-1);//删除
}
int main(){
    int n;cin >> n;
    rep(i,1,n-1){
        int u,v;cin >> u >> v;
        G[u].pb(v);G[v].pb(u);
    }
    rep(i,1,n)cin >> col[i];
    dfs(1,-1);
    dfs2(1,-1,0);
    int q;cin >> q;
    while(q--){
        int x;cin >> x;
        cout << ans[x] << endl;
    }
    return 0;
}

CF600E Lomsat gelral

求子树中颜色最多的颜色权值之和，相同数量都要加上

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 100010;
int sz[N],son[N];//字树大小、重儿子编号
ll col[N],ans[N],now,cnt[N],mx;
vector<int>G[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){
    cnt[col[u]] += op;
    if(op == 1){
        if(cnt[col[u]] > mx){
            mx = cnt[col[u]];
            now = col[u];
        }
        else if(cnt[col[u]] == mx){
            now += col[u];
        }
    }
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    cnt[col[u]]++;
    if(cnt[col[u]] > mx){
        mx = cnt[col[u]];
        now = col[u];
    }
    else if(cnt[col[u]] == mx){
        now += col[u];
    }
//    if(cnt[col[u]] == 1)now++;
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)solve(v,u,1);//添加贡献
    }
    ans[u] = now;
    if(op == 1)solve(u,f,-1),now=0,mx = 0;//删除
}
int main(){
    int n;cin >> n;
    rep(i,1,n)cin >> col[i];
    rep(i,1,n-1){
        int u,v;cin >> u >> v;
        G[u].pb(v);G[v].pb(u);
    }
    dfs(1,-1);
    dfs2(1,-1,0);
    rep(i,1,n)cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

CF570D Tree Requests

a子树中深度为b的结点能否构成回文串

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 500010;
int sz[N],son[N];//字树大小、重儿子编号
ll bit[N],ans[N],dep[N];
int SON;
vector<int>G[N];
vector
vec[N];
char s[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    if(f != -1)dep[u] = dep[f] + 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){
    bit[dep[u]] ^= (1ll << (s[u-1]-'a'));
    for(auto v : G[u]){
        if(v == f)continue;
        if(v != SON)solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0),SON = son[u]; //处理重儿子
    solve(u,f,op);
    for(auto v : vec[u]){
        int cnt = __builtin_popcount(bit[v.second-1]);
        if(cnt <= 1)ans[v.first] = 1;
    }
    SON = 0;
    if(op == 1)solve(u,f,-1);//删除
}
int main(){
//    cout << __builtin_popcount(1);//二进制中有多少个1
    int n,q;cin >> n >> q;
//    rep(i,1,n)cin >> col[i];
    rep(i,2,n){
        int x = read();
        G[x].pb(i);
    }
    scanf("%s",&s);
    rep(i,1,q){
        int x = read(),y = read();
        vec[x].pb(P(i,y));
    }
    dfs(1,-1);
    dfs2(1,-1,1);
    rep(i,1,q){
        if(ans[i])puts("Yes");
        else puts("No");
    }
    return 0;
}

CF246E Blood Cousins Return

a结点的k阶后代有多少个不同的值

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 500010;
int sz[N],son[N];//字树大小、重儿子编号
int ans[N],dep[N];
int val[N];
bitsetbit;
vector<int>G[N];
vector
vec[N];
set<int>sta[N];
multiset<int>sta2[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    if(f != -1)dep[u] = dep[f] + 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){

    if(op == 1) {
        sta[dep[u]].insert(val[u]);
//        sta2[dep[u]].insert(val[u]);
    }
    else {
        sta[dep[u]].erase(val[u]);
//        sta2[dep[u]].erase(sta2[dep[u]].find(val[u]));
//        if(sta2[dep[u]].find(val[u]) == sta2[dep[u]].end()){
//            sta[dep[u]].erase(val[u]);
//        }
    }
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    sta[dep[u]].insert(val[u]);
//    sta2[dep[u]].insert(val[u]);
    for(auto v : G[u]){
        if(son[u] != v)solve(v,u,1);
    }
    for(auto v : vec[u]){
        ans[v.first] = SZ(sta[dep[u] + v.second]);
    }
    if(op == 1)solve(u,f,-1);//删除
}
map<string,int>mp;
int tot;
vector<int>v;
int main(){
//    cout << __builtin_popcount(b);//二进制中有多少个1
    int n = read();
    rep(i,1,n){
        string str;
        int pa;
        cin >> str >> pa;
        if(!mp.count(str))mp[str] = ++tot;
        val[i] = mp[str];
        if(pa == 0)v.pb(i);
        else G[pa].pb(i);
    }
//    rep(i,1,n){
//        cout << val[i] << ' ';
//    }
//    cout << endl;
    int q = read();
    rep(i,1,q){
        int x = read(),y = read();
        vec[x].pb(P(i,y));
    }
    for(auto root : v){
        dfs(root,-1);
        dfs2(root,-1,1);
    }
    rep(i,1,q) writeln(ans[i]);
    return 0;
}

CF208E Blood Cousins

与a结点拥有共同k阶祖先的结点有多少个

（倍增找到a的k阶祖先，然后就是上一题CF246E了）

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 100010;
int sz[N],son[N];//字树大小、重儿子编号
int ans[N],dep[N];
int val[N];
int pa[N][21];
vector<int>G[N];
vector
vec[N];
set<int>sta[N];
void dfs(int u,int f){ //找重儿子
    pa[u][0] = f;
    sz[u] = 1;
    if(f != -1)dep[u] = dep[f] + 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){

    if(op == 1) {
        sta[dep[u]].insert(val[u]);
    }
    else {
        sta[dep[u]].erase(val[u]);
    }
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    sta[dep[u]].insert(val[u]);
    for(auto v : G[u]){
        if(son[u] != v)solve(v,u,1);
    }
    for(auto v : vec[u]){
        ans[v.first] = SZ(sta[dep[v.second]]) - 1;
    }
    if(op == 1)solve(u,f,-1);//删除
}
int tot;
vector<int>v;
int Find(int x,int y){ //x的y阶级祖先
    int pos = 0;
    while(y){
        if(y & 1)x = pa[x][pos];
        if(x == -1)return -1;
        y >>= 1;
        pos++;
    }
    return x;
}
int main(){
//    cout << __builtin_popcount(b);//二进制中有多少个1
    int n = read();
    rep(i,1,n){
        val[i] = i;
        int pa;
        cin >> pa;
        if(pa == 0)v.pb(i);
        else G[pa].pb(i);
    }
    for(auto root : v){
        dfs(root,-1);
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= 20;j++){
            if(pa[i][j-1] != -1) pa[i][j] = pa[pa[i][j-1]][j-1];
            else pa[i][j] = -1;
        }
    }
    int q = read();
    rep(i,1,q){
        int x = read(),y = read();
        int z = Find(x,y);
        if(z >= 1) vec[z].pb(P(i,x));
//        cout << z << ' ' << i << ' ' << x << endl;
    }
    for(auto root : v){
        dfs2(root,-1,1);
    }
    rep(i,1,q) writeln(ans[i]);
    return 0;
}

CF1009F Dominant Indices

a子树中，找到层数结点数最多的那一层

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 1000010;
int sz[N],son[N];//字树大小、重儿子编号
int ans[N],dep[N],cnt[N],mx,res,mxid;
int val[N],last;
vector<int>G[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    if(f != -1)dep[u] = dep[f] + 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){
    cnt[dep[u]] += op;
    if(op == 1 && cnt[dep[u]] >= mx){
        if(cnt[dep[u]] > mx){
            mxid = u;
            mx = cnt[dep[u]];
        }
        else if(cnt[dep[u]] == mx){
            if(dep[u] < dep[mxid]){
                mxid = u;
            }
        }
    }
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    cnt[dep[u]]++;
    if(cnt[dep[u]] >= mx){
        if(cnt[dep[u]] > mx){
            mx = cnt[dep[u]];
            mxid = u;
        }
        else if(cnt[dep[u]] == mx){
            if(dep[u] < dep[mxid]){
                mxid = u;
            }
        }
        res = 0;
    }
    last = u;
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)solve(v,u,1);
    }
    if(mxid)res = dep[mxid] - dep[u];
    ans[u] = res;
//    cout << u << ' ' << mx << ' ' << res << endl;
    if(op == 1)solve(u,f,-1),res = 0,mx = 0,mxid = 0;//删除
}

int main(){
    int n = read();
    rep(i,1,n-1){
        int u = read(),v = read();
        G[u].pb(v);G[v].pb(u);
    }
    int root = 1;
    dfs(root,-1);
//    rep(i,1,n)cout << dep[i] << ' ';
//    cout << endl;
    dfs2(root,-1,1);
    rep(i,1,n) writeln(ans[i]);
    return 0;
}

CF375D Tree and Queries

a子树中出现次数>=k的颜色有多少种

#include
#include<set>
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define fi first
#define se second
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define N 101000
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair
#define pi acos(-1)
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define lowbit(x) (x&(-x))
#define SZ(x) ((ll)(x).size())
#define met(a,x) memset(a,x,sizeof(a))
#define openin(x) freopen(x, "r", stdin)
#define openout(x) freopen(x, "w",stdout)
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define bep(i,a,b) for(ll i = a;i >= b;i--)
#define ios() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll mod = 1e9+7;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
int days[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int is_leapyear(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
inline ll read() {
    ll x = 0, sign = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return sign * x;
}
inline void write(ll x){
    char r[30];
    int t = 0;
    if(x < 0){
        x = -x;
        putchar('-');
    }
    do{
        r[t++] = x % 10 + '0';
        x /= 10;
    }while(x);
    while(t)putchar(r[--t]);
}
inline void writesp(ll x){
    write(x);
    putchar(' ');
}
inline void writeln(ll x){
    write(x);
    putchar('\n');
}
inline void writedo(double x,int op){
    cout << fixed < endl;
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 100010;
int sz[N],son[N];//字树大小、重儿子编号
int ans[N],dep[N],cnt[N],num[N];//答案、深度、cnt[i]代表i颜色出现多少次，num[i]代表出现次数>=i的有多少个
int col[N];//i点的颜色
vector<int>G[N];
vector
vec[N];
void dfs(int u,int f){ //找重儿子
    sz[u] = 1;
    if(f != -1)dep[u] = dep[f] + 1;
    for(auto v : G[u]){
        if(v == f)continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]){
            son[u] = v;
        }
    }
}
void solve(int u,int f,int op){
    if(op == -1){
        num[cnt[col[u]]] -= 1;
        cnt[col[u]] -= 1;
    }
    if(op == 1){
        cnt[col[u]] += 1;
        num[cnt[col[u]]] += 1;
    }
    for(auto v : G[u]){
        if(v == f)continue;
        solve(v,u,op);
    }
}
void dfs2(int u,int f,int op){
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)dfs2(v,u,1); //处理轻儿子，消除影响
    }
    if(son[u])dfs2(son[u],u,0); //处理重儿子
    cnt[col[u]]++;//col[u]出现次数+1
    num[cnt[col[u]]]++;//出现cnt[col[u]]次，次数+1
    for(auto v : G[u]){
        if(v == f)continue;
        if(son[u] != v)solve(v,u,1);
    }
    for(auto v : vec[u]){
        ans[v.first] = num[v.second];
    }
    if(op == 1)solve(u,f,-1);//删除
}

int main(){
    int n = read(),q = read();
    rep(i,1,n)col[i] = read();
    rep(i,1,n-1){
        int u = read(),v = read();
        G[u].pb(v);G[v].pb(u);
    }
    rep(i,1,q){
        int x = read(),y = read();
        vec[x].pb(P(i,y));
    }
    int root = 1;
    dfs(root,-1);
    dfs2(root,-1,1);
    rep(i,1,q) writeln(ans[i]);
    return 0;
}

https://codeforces.com/contest/291/problem/E、CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths、wannafly Day2 E 阔力梯的树

掌握套路！

图论

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签