首页 > 其他分享 >P5593 题解

P5593 题解

时间:2024-10-05 23:00:32浏览次数:8  
标签:__ sz ch 颜色 int 题解 子树 P5593

题目

分析

首先考虑什么样的颜色能被链覆盖。

容易想到当某种颜色恰巧在一条链上会被覆盖。

所以只需要判断一种颜色是否能构成链即可,链的贡献也很好计算。

算法

考虑链的性质:有且仅有两个端点。

凭借这个性质,可以判断一种颜色是否在一条链上。

在 dfs 中考虑各种情况。

假设一个点 \(u\),其颜色为 \(c\),有以下 \(2\) 种情况判断 \(u\) 是否为端点。

  1. 如果 \(u\) 的子树中没有颜色 \(c\) 的节点,那么 \(u\) 点是一个端点。
  2. 满足两个条件。
    1. 除了 \(u\) 的子树没有颜色 \(c\) 的节点。
    2. \(u\) 的所有儿子中,只有一个儿子的子树中有颜色 \(c\)。

判断端点数量是否等于 \(2\),等于 \(2\) 说明该种颜色恰好构成一条链。

还有一个特殊情况:某个颜色可能只有一个点,需要直接算答案。

如果是一条链的话,假设两条节点为 \(p, q\),对答案的贡献有两种情况。

  1. 如果 \(p, q\) 均是满足上述第 \(1\) 种情况的,答案为 \(sz_p \times sz_q\) 。
  2. 如果 \(p\) 是满足上述第 \(2\) 种情况的,考虑一下,因为 \(p\) 的所有儿子中,只有一个儿子的子树中有颜色 \(c\),假设该儿子为 \(pos\),所以 \(p\) 的其他儿子的子树中的节点也能对答案有贡献,故答案为 \((n - sz_{pos}) \times sz_q\)。

如何实现见代码。

#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif

#include <iostream>
#include <cstdio>
typedef long long LL;

using namespace std;

void RD() {}
template<typename T, typename... U> void RD(T&x, U&... arg) {
    x = 0; int f = 1; char ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-') ch = getchar(); ch = getchar(); }
    while (ch <= '9' && ch >= '0') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    x *= f; RD(arg...);
}

void WT() {}
template<typename T> void WT(T x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) WT(x / 10);
    putchar(x % 10 + '0');
}

const int N = 3e6 + 5;

#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

int head[N], ver[N << 1], Next[N << 1], _tot = 1;
int n, a[N], tot[N], nos[N], enos[N], cnt[N], sz[N];
LL ans, ans1[N], ans2[N];

void add(int u, int v) {
    ver[++_tot] = v;
    Next[_tot] = head[u], head[u] = _tot;
}

/*
如果 flag == 1,才能判断为端点
这是由 flag 的增加方式决定的
*/
void dfs(int u, int _f) {
    int c = a[u], flag = 0, pos = 0;
    int k = cnt[c];
    sz[u] = 1;

    for (int i = head[u]; i; i = Next[i]) {
        int v = ver[i];
        if (v == _f) continue;
        int la = cnt[c];
        dfs(v, u);
        ans1[u] += 1LL * sz[u] *sz[v];
        sz[u] = sz[u] + sz[v];
        if (la != cnt[c]) flag++, pos = v; // 与判断是否为端点的条件2相关
    }                                      // 如果该条件被满足两次pos自然就无用了

    ans1[u] += 1LL * sz[u] * (n - sz[u]);
    if (k || cnt[c] != tot[c] - 1) flag++; // 与判断是否为端点的条件1相关
    cnt[c]++;

    if (flag == 1) {
        if (!enos[c]) nos[c] = u;
        else {
            int p = pos ? n - sz[pos] : sz[u];
            ans2[c] = 1LL * p * sz[nos[c]];
        }
        enos[c]++;
    }
}

int main() {
#ifdef FRZ_29
    freopen("read.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif

    RD(n);

    LF(i, 1, n) {
        RD(a[i]); tot[a[i]]++; nos[a[i]] = i;
    }

    LF(i, 1, n - 1) {
        int u, v; RD(u, v);
        add(u, v), add(v, u);
    }

    dfs(1, 0);

    LF(i, 1, n) {
        if (tot[i] == 0) ans ^= 1LL * n * (n - 1) / 2;
        else if (tot[i] == 1) ans ^= ans1[nos[i]];
        else if (enos[i] == 2) ans ^= ans2[i];
        else ans ^= 0;
    }

    WT(ans);
    return 0;
}

七月流火,九月授衣。

标签:__,sz,ch,颜色,int,题解,子树,P5593
From: https://www.cnblogs.com/FRZ29/p/18448657

相关文章

  • P10418 [蓝桥杯 2023 国 A] 相连的边 题解
    一个比较有趣的树形DP,情况比较多。【题目简述】给定一棵树,求三条相连的边,其边权之和最大。【思路】以X代表当前节点,S表示儿子,G表示孙子,P表示父节点。首先把树建出来,在以下图中,我们模拟二号点的DP过程,考虑以下几种情况:有一条边指向父节点时FG(FatherGrandson):一......
  • 数列 题解
    题意给出一张联通图,图上每个点有红蓝两色,给每一条边都赋一个权值,使得所有的红边构成一颗最小生成树,且权值是\(1\)到\(m\)的排列,求字典序最小的情况。题解对于一条蓝边,其权值一定小于除它以外全是红边的环上的所有红边的权值(有点绕),否则就构不成一颗生成树。所以只需要按顺......
  • CF946G Almost Increasing Array 题解
    题目传送门前置知识最长不下降子序列|权值树状数组及应用解法若将\(\{a\}\)变成严格递增序列,至少需要更改\(n\)减去\(\{a_{i}-i\}\)的最长不下降子序列长度个数。证明对于\(a_{i},a_{j}(i<j)\)若都在最终的严格递增序列里,则有\(a_{i}-a_{j}\lei-j\),即\(......
  • PHP报错getimagesize(): SSL operation failed with code 1问题解决方案
    这个PHP错误通常发生在尝试通过HTTPS协议获取图像时,由于缺少或过期的CA证书导致SSL连接验证失败。以下是详细的解决方案:解决方案一:更新CA证书下载最新的CA证书访问 curl官方提供的CA证书 页面下载 cacert.pem 文件。上传证书文件将下载的 cacert.......
  • U486684 「INOI2016」Brackets 题解
    首先对于回文&括号有一个经典转移:枚举分割点+区间两个端点讨论此题也是如此首先枚举分割点十分套路,如下\[dp_{i,j}=\max_{k=i}^{j-1}dp_{i,k}+dp_{k+1,j}\]如果两个端点相同\[dp_{i,j}=dp_{i+1,j-1}+v_i+v_j\]还有一个转移对于一个区间,因为是子序列,所以一个区间的子区间......
  • qoj9230 Routing K-Codes 题解
    首先这个图肯定不能有环,也不能有度数大于\(3\)的点。也就是说这是一颗二叉树。我们假设父亲都比儿子小,根节点的值最小。那么假设\(u\)点的值为\(x\),它的儿子的值一定是\(\{2x,2x+1\}\)的子集。会发现\(u\)的子树内的权值和是一个关于\(x\)的一次函数。而且无论两个儿......
  • CF1648F Two Avenues 题解
    非常好题目,使我代码旋转。思路考虑什么样的边有贡献。我们首先提出原图的一个dfs树。处理出经过关键点的树上路径在每一条树边的经过次数\(v_i\)。我们选点会有以下几种情况。选两条割边\(i,j\),由于割边肯定是树边,所以答案就是\(v_i+v_j\)。选一条只被一条非树边覆盖......
  • P9611 题解
    题目大意从题目可知,本题要求求出\(l\simr\)的因子个数和。题目分析我们可以将这个问题分解为两个问题,变成求\(1\simr\)的因子个数和减去\(1\siml-1\)的因子个数和,然后我们考虑如何求\(1\simn\)的因子个数和首先,如果正着做很难的话,我们可以考虑反着做。对于一个数\(......
  • CF1108F题解
    传送门:https://codeforces.com/problemset/problem/1108/F求出最小生成树后处理出任意两点间边的最大值,这里可以用倍增或者树刨。然后用不在生成树上的边去替换,如果边权和边两端点路径最大边值相同则最小生成树不唯一,需要将边权\(+1\)。实现比较简单,写了一遍就过了。#include<b......
  • 题解:CF704B Ant Man
    从这来的,套路都一样,预设型DP。把那个式子拆开,看每个数单独的贡献。一个数比它左边的数小,它的贡献就是:\(-x_i+b_i\)比它左边的数大,它的贡献就是:\(x_i+a_i\)比它右边的数小,它的贡献就是:\(-x_i+d_i\)比它右边的数大,它的贡献就是:\(x_i+c_i\)即:intGl(inti){//>......