#C241029D. 鼓手(drum)
标签（Label）
- 树上笛卡尔树
网址（Website）
Practice Coding Problem (codechef.com)
题目（Problem）
样例
输入数据 1
7
2 5
3 5
4 1
5 4
6 1
7 4输出数据 1
10样例2∼4
见选手目录下的 drum/drum[2-4].in 与 drum/drum[2-4].ans。
给出的三个样例分别满足测试点 $1\sim3, 7\sim9, 10\sim14$ 的性质。
题解（Solution）
$\qquad$具体讲一下如何实现树上笛卡尔树的建树的。
$\qquad$对于大根树，我们先从最小的编号开始枚举树节点，并且对于每个编号遍历所有编号小于当前编号的边，由于我们要满足 $\text{Kruskal}$ 重构树的性质，我们每次连边的时候都要连当前点 $x$ 到 $y$ 的连通块的最大编号，这个可以用并查集来维护，在每次连边的时候直接把儿子向父亲连边即可。
$\qquad$那后面怎么处理呢？建立大根树和小根树之后，观察可以发现，只有在两棵树上都是祖先关系（即 $\verb!lca(x,y)==x!$ 或 $\verb!lca(x,y)==y!$ ），我们先遍历大根树，并且求出 $\text{dfn}$ 序，则当前点的儿子编号一定小于自己。遍历小根树时，每遍历到一个节点就把这个节点的 $\text{dfn}$ 加入树状数组中，访问结束后在除去，询问时询问当前节点的子树，这些数一定是当前点的儿子或孙子，此时在树状数组上存在的节点又满足和当前节点在大根树上是子孙关系，计入贡献即可。
$\qquad$时间复杂度 $O(n\log n)$ 。
出题者题解
【算法分析】
【算法一】
枚举路径，判断合法。
时间复杂度根据实现 $O(n^3 \sim n^2)$，期望得分 $12 \sim 24$。
【算法二】
当树退化为菊花图时，长度为 $1$ 的路径一定合法。
若长度为 $2$，记其经过点为 $a, c, b$，则合法需满足 $a < c < b$，记根为 $r$，易得这部分答案为 $(r-1) \times (n-r)$。
时间复杂度根据实现 $O(n \sim 1)$，期望得分 $12$。
结合算法一可以得到 $36$ 分。
【算法三】
当树退化为链时，相当于合法的区间左右端点需要为区间 $\min/\max$。
使用单调栈求出 $l_i, r_i, L_i, R_i$ 表示 $i$ 作为最小值的区间 $u, v$ 要满足 $u \in [l_i, i], v \in [i, r_i]$，作为最大值要满足 $u \in [L_i, i], v \in [i, R_i]$。
枚举左端点 $u$，若 $u$ 为 $\min$ 右端点 $v$ 的限制为 $u < v \leq r_u, L_v \leq u$，可以离线用树状数组查询。 $u = \max$ 的情况是类似的。
时间复杂度 $O(n \log n)$，期望得分 $20$。
结合算法一和算法二可以得到 $56$ 分。
【算法四】
题目中的条件等价于： $a$ 为链上最小值，$b$ 为链上最大值。
考虑建出原树的点 $Kruskal$ 重构树（我愿称之为树上笛卡尔树），也就是每次取出连通块的最值作为根，然后删去根裂成若干个连通块，递归构造这些连通块，最后在新图中将这些连通块的根与整个连通块的根连边。
容易发现，这样建出的新树满足 $a, b$ 在原树上的链上最值等于新树上的 $lca(a, b)$。
于是建出最小值的树和最大值的树，条件变为： $a, b$ 在两棵树上都要是祖先关系。
求出一棵树的 $dfn$，在另一棵树上 $dfs$，维护当前点到根路径上所有点出现的 $dfn$，合法的祖先个数可以直接区间查询。
时间复杂度 $O(n \log n)$，期望得分 $100$。
代码（Code）
36分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i==)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define inn(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
vector<int> ft[N];
int n,ans;
struct wo_yao_da_bao_li{
inline bool check0(){return n<=5000;}
inline bool check1(){return n==200001;}
void dfs_ans(int x,int fa,int l,int r,int rt){
int L = min(x,rt), R = max(x,rt);
l=min(l,x), r=max(r,x);
if(x!=rt && inn(l,L,R) && inn(r,L,R)) ans++;
for(auto y:ft[x]){
if(y==fa) continue;
dfs_ans(y,x,l,r,rt);
}
}
void solve0(){
For(i,1,n) dfs_ans(i,i,i,i,i);
printf("%lld\n",ans/2);
}
void solve1(){
int rt = 0;For(i,1,n) if(ft[i].size() > ft[rt].size()) rt = i;
int ans = n-1 + (rt-1)*(n-rt);
printf("%lld\n",ans);
}
}Q;
void Solve(){
n = rd();For(i,1,n-1){
int x=rd(),y=rd();
ft[x].emplace_back(y);
ft[y].emplace_back(x);
}
if(Q.check0()) return Q.solve0();
if(Q.check1()) return Q.solve1();
Q.solve0();
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("drum.in","r",stdin);
freopen("drum.out","w",stdout);
int T=1;double Tim=clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}100分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define inn(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
vector<int> e[N],ft[N],gt[N];
int n,ans;
struct dsu{
int fa[N];void init(){iota(fa+1,fa+n+1,1);}
inline int find(int x){
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}inline void merge(int x,int y){fa[find(y)]=find(x);}
}F;
struct BIT{
int c[N];
void init(){memset(c,0,sizeof c);}
inline int lbt(int i){return i&(-i);}
void update(int x,int v){for(int i=x;i<=n;i+=lbt(i)) c[i]+=v;}
int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
inline int calc(int l,int r){return ask(r)-ask(l-1);}
}B;
int st[N],ed[N],idx;
void dfs_dfn(int x){
st[x] = ++idx;
for(auto y:ft[x]) dfs_dfn(y);
ed[x] = idx;
}
void dfs_ans(int x){
ans += B.calc(st[x],ed[x]);
B.update(st[x],1);
for(auto y:gt[x]) dfs_ans(y);
B.update(st[x],-1);
}
void Solve(){
n = rd();For(i,1,n-1){
int x=rd(),y=rd();
e[x].emplace_back(y);
e[y].emplace_back(x);
}
F.init();
For(x,1,n) for(auto y:e[x]){//´ó¸ùkruskal
if(x>y){
ft[x].emplace_back(F.find(y));
F.merge(x,y);
}
}
F.init();
Rof(x,n,1) for(auto y:e[x]){//´ó¸ùkruskal
if(x<y){
gt[x].emplace_back(F.find(y));
F.merge(x,y);
}
}
dfs_dfn(n), dfs_ans(1);
printf("%lld\n", ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("drum.in","r",stdin);
freopen("drum.out","w",stdout);
int T=1;double Tim=clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
