本文涉及的知识点CDFS[CSP-S2019] 括号树题目背景本题中合法括号串的定义如下()是合法括号串。如果A是合法括号串则(A)是合法括号串。如果AB是合法括号串则AB是合法括号串。本题中子串与不同的子串的定义如下字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l ll与终止位置r rr来表示记为S ( l , r ) S (l, r)S(l,r)1 ≤ l ≤ r ≤ ∣ S ∣ 1 \leq l \leq r \leq |S |1≤l≤r≤∣S∣∣ S ∣ |S |∣S∣表示 S 的长度。S的两个子串视作不同当且仅当它们在S中的位置不同即l ll不同或r rr不同。题目描述一个大小为n nn的树包含n nn个结点和n − 1 n - 1n−1条边每条边连接两个结点且任意两个结点间有且仅有一条简单路径互相可达。小 Q 是一个充满好奇心的小朋友有一天他在上学的路上碰见了一个大小为n nn的树树上结点从1 ∼ n 1 \sim n1∼n编号1 11号结点为树的根。除1 11号结点外每个结点有一个父亲结点u uu2 ≤ u ≤ n 2 \leq u \leq n2≤u≤n号结点的父亲为f u f_ufu1 ≤ f u u 1 ≤ f_u u1≤fuu号结点。小 Q 发现这个树的每个结点上恰有一个括号可能是(或)。小 Q 定义s i s_isi为将根结点到i ii号结点的简单路径上的括号按结点经过顺序依次排列组成的字符串。显然s i s_isi是个括号串但不一定是合法括号串因此现在小 Q 想对所有的i ii1 ≤ i ≤ n 1\leq i\leq n1≤i≤n求出s i s_isi中有多少个互不相同的子串是合法括号串。这个问题难倒了小 Q他只好向你求助。设s i s_isi共有k i k_iki个不同子串是合法括号串 你只需要告诉小 Q 所有i × k i i \times k_ii×ki的异或和即( 1 × k 1 ) xor ( 2 × k 2 ) xor ( 3 × k 3 ) xor ⋯ xor ( n × k n ) (1 \times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)(1×k1)xor(2×k2)xor(3×k3)xor⋯xor(n×kn)其中x o r xorxor是位异或运算。输入格式第一行一个整数n nn表示树的大小。第二行一个长为n nn的由(与)组成的括号串第i ii个括号表示i ii号结点上的括号。第三行包含n − 1 n − 1n−1个整数第i ii1 ≤ i n 1 \leq i \lt n1≤in个整数表示i 1 i 1i1号结点的父亲编号f i 1 f_{i1}fi1。输出格式仅一行一个整数表示答案。样例 #1样例输入 #15 (()() 1 1 2 2样例输出 #16提示【样例解释1】树的形态如下图将根到 1 号结点的简单路径上的括号按经过顺序排列所组成的字符串为(子串是合法括号串的个数为0 00。将根到 2 号结点的字符串为((子串是合法括号串的个数为0 00。将根到 3 号结点的字符串为()子串是合法括号串的个数为1 11。将根到 4 号结点的字符串为(((子串是合法括号串的个数为0 00。将根到 5 号结点的字符串为(()子串是合法括号串的个数为1 11。【数据范围】括号 DFS令节点i对应的字符是ss[i]。s[i]记录根节点到形成的字符串t(j…i)记录i的祖先节点j到i形成的字符串。合法括号的另一种定义字符(的分值1字符)的分值-1。s的任意前缀分值0s的分值等于0。c[i] 记录s[i]记录s[i]合法后缀数量d[i] 记录s[i]记录合法子串数量。d[i] d[i的父节点]c[i]。DFS求c[cur]v[i]包括j表示t(j…cur)的分值是i。v[i]只记录以cur结尾的子字符串。cc ss[cur]是分值如果把v[i][j] 全部改成v[icur][j]那时间复杂度是O(nn)。我们不修改v[i][j]只将iAddch。if(cc-iAdd0) { v[cc-iAaa].Add(cur);}if(-1-iAdd 0) v[-1-iAdd]的元素移动 哈希集合inv。c[i] v[-iAdd].size();DFS子节点inv 存在 cur 删除。否则在v中删除。iAdd - cc代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}classSolution{public:longlongAns(string s,vectorintparent){constintNs.length();parent.insert(parent.begin(),0);for(autoi:parent){i--;}vectorvectorintchilds(N);for(inti1;iN;i){childs[parent[i]].emplace_back(i);}vectorlonglongc(N),d(N);unordered_mapint,longlongmSuffVCnt;functionvoid(int,int)DFS[](intcur,intiAdd){constautocvalue((s[cur])?1:-1;iAddcvalue;mSuffVCnt[cvalue-iAdd];//s[cur...cur]数量1autocntErasemSuffVCnt[-1-iAdd];mSuffVCnt.erase(-1-iAdd);//权值-1非法删除c[cur]mSuffVCnt[-iAdd];if(0!cur){d[cur]d[parent[cur]];}d[cur]c[cur];for(constautochi:childs[cur]){DFS(chi,iAdd);}mSuffVCnt[-1-iAdd]cntErase;mSuffVCnt[cvalue-iAdd]--;iAdd-cvalue;};DFS(0,0);longlongans0;for(inti0;iN;i){ans^(i1)*d[i];}returnans;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintn;cinn;autosReadchar(n);s.emplace_back(0);autoparReadint(n-1);autoresSolution().Ans(s.data(),par);#ifdef_DEBUG//printf(K%d, K);//Out(b, b);//Out(c, c);#endif// DEBUGcoutres;return0;}单元测试vectorintparent;string s;TEST_METHOD(TestMethod11){parent{1,1,2,2},s(()();autoresSolution().Ans(s,parent);AssertEx(6LL,res);}扩展阅读我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。