LOJ6669 Nauuo and Binary Tree 解题笔记
题目来源 LOJ6669 Nauuo and Binary Tree 题意简述 这是一道交互题。 有一棵以 111 为根的二叉树，你可以询问任意两点之间的距离，求出每个点的父亲。 节点数不超过 300030003000 ，你最多可以进行 300003000030000 次询问。 解题思路 观察数据范围可知，本题可以接受 O(n2)O(n^2)O(n2) 的时间复杂度，但关键在于如何降低询问复杂度。 显然，本题需要由浅到深地逐层加入节点，否则就无从下手。 设当前待插入的节点为 xxx 。 又由于本题的树满足二叉树的特殊性质，所以可以考虑 xxx 是去左子树还是右子树。 如果暴力询问 xxx 到左儿子和右儿子的距离，选择走哪一棵子树，最坏询问复杂度为 O(n2)O(n^2)O(n2) ，具体情况如下图。 ..
更多P3384 【模板】重链剖分/树链剖分 树剖提高模板
题目来源 P3384 【模板】重链剖分/树链剖分 题意简述 已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。 2 x y，表示求树从 xxx 到 yyy 结点最短路径上所有节点的值之和。 3 x z，表示将以 xxx 为根节点的子树内所有节点值都加上 zzz。 4 x 表示求以 xxx 为根节点的子树内所有节点值之和 1≤N≤1051\le N \leq {10}^51≤N≤105，1≤M≤1051\le M \leq {10}^51≤M≤105，1≤R≤N1\le R\le N1≤R≤N，1≤P≤231−11\le P \le 2^{31}-11≤P..
更多P3379 最近公共祖先 树剖基础模板
来不及解释了，直接上代码 #include<bits/stdc++.h> #define ll long long #define N 500100 using namespace std; ll n,m,s,x,y,a,b; vector<ll> g[N]; bool vis[N]; ll fa[N],dep[N],siz[N],son[N]; ll top[N],tot,dfn[N],rnk[N]; inline void dfs1(ll root, ll depth){ vis[root] = true; dep[root] = depth; ll maxSon = 0; for(auto soni : g[root]){ if(vis[s..
更多