当前位置: 首页 > news >正文

题解:P10107 [GDKOI2023 提高组] 树

题意:很简单了,不再赘述。

做法:

题解中好像有很牛的 bfs 序做法,太困难了,我只会暴力还常数很大的长链剖分。

首先看到是个 k 邻域问题,那基本上要不然是 bfs 序转化要不然是长链剖分,我只会后面这个东西所以考虑长链剖分。

然后再看权值,权值是一个异或的形式,那么考虑长链剖分的时候直接向上合并,这样非常麻烦,基本上维护不了异或值的变化,所以考虑拆位,这样我们就可以只用管这一位上的 \(0/1\) 的个数即可。

考虑对于一个节点 \(u\),当前是计算二进制下第 \(k\) 位的答案,他深度中应该是一段长度为 \(2^k\) 的需要权值这一位为 \(1\) 的,一段需要权值这一位为 \(0\) 的去贡献,所以我们长链剖分考虑维护的是 \(u\) 子树中深度为 \(x\)\(0/1\) 有多少个。

如何计算对答案的贡献?显然我们不能暴力一段一段跳往后找,但是我们发现,我们其实可以把一段 0 和一段 1 放在一起计算,也就是说,我们可以记一个 \(f_i\) 代表深度为 \(i\),深度 \(\ge i\) 的异或值这一位为 \(1\) 的有多少个,然后用 \(f_{i} = f_{i+2^{k+1}}+count(i,i+2^k-1, 1)+count(i+2^k,i+2^{k+1}-1,0)\) 去计算,其中 \(count(l,r,x)\) 代表深度在 \([l,r]\) 内有多少个为 \(x\) 的。

计算答案的时候,我们先整段整段按 \(2^{k+1}\) 一个周期地加,这个可以直接用 \(f\) 做减法 \(O(1)\) 得到,然后再用 \(count\) 地方式计算出来散块的贡献。

如何计算 \(count\)?前缀和的话对于我们长链剖分来说太不友好了,合并上来复杂度是长链的,所以我们考虑用后缀和维护就可以了。

有点卡常,一点卡常小技巧:

  1. 不要用 dfs,改成按 dfn 循环。

  2. 不用 vector,什么都别用 vector,不知道为什么特别慢。

  3. 不用维护深度为 \(x\) 的信息,直接维护后缀和就可以了,常数可以减半。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, v[maxn], p[maxn], q;
vector<int> e[maxn], qry[maxn];
int mxd[maxn], son[maxn];
void dfs1(int u) {for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];dfs1(v);if(mxd[son[u]] <= mxd[v])son[u] = v;mxd[u] = max(mxd[u], mxd[v] + 1);}
//	cout << u << " " << son[u] << " " << mxd[son[u]] << " " << mxd[u] << endl;
}
int suf[maxn][2];
int id[maxn], tot, bg[maxn], ed[maxn], x[maxn], l[maxn];
long long res[maxn];
inline int cal(int u, int l, int r, int k) {r = min(r, ed[u]);if(l > r)return 0;//cout << u << " " << l << " " << r << " " << suf[u][k][l] << endl;return suf[l][k] - (r == ed[u] ? 0 : suf[r + 1][k]);
}
int ans[maxn], cnt;
vector<int> pos[maxn];
inline void renew(int u, int t, int k) {int mx = 0;//cout << u << " " << val[u][0].size() << " " << id[u] << " " << mxd[7] << endl;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == son[u])continue;for (int j = 0; j < mxd[v] + 1; j++)suf[id[u] + j + 1][0] += suf[id[v] + j][0],suf[id[u] + j + 1][1] += suf[id[v] + j][1],ans[id[u] + j + 1] += ans[id[v] + j];mx = max(mx, mxd[v] + 1);}
//	cout << u << endl;if(id[u] != ed[t])suf[id[u]][0] = suf[id[u] + 1][0],suf[id[u]][1] = suf[id[u] + 1][1];suf[id[u]][0] += 1 - ((v[u] >> k) & 1), suf[id[u]][1] += (v[u] >> k) & 1; for (int i = 0; i >= 0; i--) {ans[id[u] + i] = (id[u] + i + (1 << k + 1) > ed[t] ? 0 : ans[id[u] + i + (1 << k + 1)]) + cal(t, id[u] + i, id[u] + i + (1 << k) - 1, 1) + cal(t, id[u] + i + (1 << k), id[u] + i + (1 << k + 1) - 1, 0);}
//	cout << u << " " << ans[id[u]] << " " << k << endl;
}
long long tv[35];
void solve(int k) {if(k == 0) {for (int u = 1; u <= n; u++) {if(son[p[u]] != u) {for (int p1 = u; p1; p1 = son[p1])pos[u].push_back(p1), id[p1] = ++tot;bg[u] = id[u], ed[u] = tot;}}}int cnt = 0;for (int u = n; u >= 1; u--) {if(son[p[u]] == u)continue;for (int i = bg[u]; i <= ed[u]; i++)suf[i][0] = suf[i][1] = ans[i] = 0;//	cout << u << " " << cnt << endl;//	cout << k << " " << u << endl;for (int i = pos[u].size() - 1; i >= 0; i--) {//	cout << i << " adsf" << pos[u][i] << " " << pos[u].size() << endl;renew(pos[u][i], u, k);for (int j = 0; j < qry[pos[u][i]].size(); j++) {int idp = qry[pos[u][i]][j];int kt = (l[idp] >> (k + 1)) << (k + 1), bt = (l[idp] & tv[k + 1]);res[idp] += 1ll * (1 << k) * (ans[id[pos[u][i]]] - ans[id[pos[u][i]] + kt] + (bt >= (1 << k) ? cal(u, bg[u] + i + kt, bg[u] + i + kt + (1 << k) - 1, 1)+ cal(u, bg[u] + i + kt + (1 << k), bg[u] + i + kt + bt, 0) : cal(u, bg[u] + i + kt, bg[u] + i + kt + bt, 1)));}	}
//		for (int i = 0; i < pos[u].size(); i++)
//			cout << suf[bg[u] + i][0] << " ";
//		cout << endl;}
}
int read() {int sum = 0;char c = getchar();while(!isdigit(c))c = getchar();while(isdigit(c))sum = sum * 10 + c - '0', c = getchar();return sum;
}
void write(long long x) {if(x <= 9) {putchar(x + '0');return ;}write(x / 10);putchar(x % 10 + '0');
}
signed main() {
//	freopen("test.in", "r", stdin);
//	freopen("baoli.out", "w", stdout);
//	freopen("P10107_2.in", "r", stdin);
//	freopen("P10107_2.ans", "w", stdout);clock_t st = clock();mxd[0] = -1;n = read();for (int i = 1; i <= n; i++)v[i] = read();for (int i = 2; i <= n; i++)p[i] = read(), e[p[i]].push_back(i);q = read();dfs1(1);for (int i = 1; i <= q; i++)x[i] = read(), l[i] = min(mxd[x[i]], read()), qry[x[i]].push_back(i);// 只做 0 ~ 19 位,更高的没有意义for (int i = 0; i <= 31; i++)tv[i] = (1ll << i) - 1;for (int i = 0; i <= 29; i++) {solve(i);
//		if(i == 0) {
//			for (int j = 0; j < 5; j++)
//				cout << val[1][1][j] << " " << suf[1][1][j] << endl;
//			cout << ans[6] << endl;
//		}}//	cout << ans[pos[1][0]] << " " << pos[1][2] << " " << suf[1][1][2] << " " << cal(1, 3, 3, 0) << endl;//	cout << cnt << endl;
//	cout << tv[31] - tv[20] << endl;cerr << (double)(clock() - st) / CLOCKS_PER_SEC << endl;for (int i = 1; i <= q; i++)write(res[i]), putchar('\n');return 0;
}
/*
7
1 1 1 1 1 1 1
1 1 2 2 3 3
4
1 0
1 1
1 2
2 1
*/
http://www.hskmm.com/?act=detail&tid=17743

相关文章:

  • Gitee Wiki:AI赋能的下一代研发知识管理平台如何重塑软件行业协作范式
  • COLMAP 安装在ubuntu20服务器上问题解决全记录
  • 完整教程:Prompt Tuning提示词微调工程
  • Autodesk Moldflow 2026下载地址与安装教程
  • 程序员利用Python分析股票赚钱,开发了股票行情看板
  • 9.26
  • K8S Deployment 学习
  • 全面掌握 Py2neo 与 Neo4j:从容器化部署到高级应用实战 - 详解
  • 原型
  • 集训队作业1——qoj#11722
  • 如何设置将浏览器网页临时禁用网页mathjax渲染直接查看latex编译前的文本
  • 《IDEA 2025破解 长效使用指南:2099 年有效期配置实战之JetBrains全家桶有效》​
  • Helloworld
  • 基于菲涅尔积分的角锥喇叭方向图计算
  • Flask的ORM工具SQLAlchemy
  • 使用 Rust 和 Tesseract OCR 实现英文数字验证码识别
  • 构建复合AI系统以实现可扩展工作流
  • Python HTTPS 爬虫实战,requests aiohttp Selenium 抓取技巧、HTTPS 问题与抓包调试(python https爬虫、反爬、抓包、证书处理)
  • GreatSQL 优化技巧:最值子查询与窗口函数相互转换
  • Windows Time 时间同步时出错
  • CCS开发环境和TMS320系列DSP实现IP-IQ谐波与无功电流检测
  • 多机动模型PHD滤波算法
  • Navicat17无限试用重置14天
  • 基于Electron的Web打印解决方案:web-print-pdf技术分享
  • CF455D Serega and Fun
  • 实验任务
  • 61.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--新增功能--提取金额 - 实践
  • 使用 Ansible 部署 Elasticsearch 集群
  • 免费无广告!这款开源工具让文件转换像复制粘贴一样简单!
  • 时序InSAR形变结果合并操作说明 - ENVI