前言
想了巨大久的正解，最后还是只能胡个昨天刚学的点分治暴力qwq。
题目
( m 2s 512MB.)
( t PPL) 在 ( m ZBQC) 随机游走累了，现在他想尝试一些好康的路径。
由于众所周知的原因，( m ZBQC) 非常小，小的两点之间有且仅有一条路径，也就是说可以视为一棵树。
( t PPL) 认为好康的路径 (x ightarrow y) 应该满足 (x) 是路径上编号最小的点，(y) 是路径上编号最大的点。
( t PPL) 决定你告诉他有多少条好康的路径后就把这些路径全部走一遍，你能告诉他吗？
(1le nle 2 imes 10^6.)
讲解
现在是乱扯部分，如果要直接看正解请往下滑。
佛了，最近几天做点分治人麻了，看到这道题就想点分治，最后试图 (O(n)) 解决二维偏序无果，只能胡了个 (O(nlog_2^2n)) 的暴力，拿到了 (60pts.)
我已经迫不及待想讲我的点分治做法了。
首先直接点分治，然后考虑过 (u) 的路径咋算贡献。考虑处理出一下两种以 (u) 为一端，(v) 为另外一端的路径：
- (v) 是这条路径的最大值。
- (v) 是这条路径的最小值。
单链很好算答案，这里我们讲一讲怎么把两条链拼起来算答案。
假如我们有第一类路径 (a) 和第二类路径 (b)，他们能拼起来当且仅当 (a_v) 是两条路径的最大值，(b_v) 是两条路径的最小值。
我们对这两种路径都记录一下它们的最大值和最小值，那么它们应该满足这个关系：(b_{min}<a_{min}<a_{max}<b_{max}.)
但事实上我们只用考虑 (b_{min}<a_{min}) 和 (a_{max}<b_{max}) 这两个限制，因为其它限制一定满足。
然后发现这就是二维偏序，直接排序+树状数组搞定，注意在同一棵子树内的不能算，所以要减掉。总时间复杂度为 (O(nlog_2^2n))。
没错，正如这篇文章所提到的，我试图在线性时间内解决二维偏序，这样复杂度就是 (O(nlog_2n)) 了，哈哈！
挂一份暴力以证明我没在胡扯
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 2000005;
int n;
LL ans;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot;
struct edge
{
int v,nxt;
}e[MAXN<<1];
void Add_Edge(int x,int y)
{
e[++tot] = edge{y,head[x]};
head[x] = tot;
}
void Add_Double_Edge(int x,int y)
{
Add_Edge(x,y);
Add_Edge(y,x);
}
bool vis[MAXN];
int MAX[MAXN],siz[MAXN],rt;
void getrt(int x,int fa,int S)
{
siz[x] = 1; MAX[x] = 0;
for(int i = head[x],v; i ;i = e[i].nxt)
{
if((v = e[i].v) == fa || vis[v]) continue;
getrt(v,x,S);
siz[x] += siz[v];
MAX[x] = Max(MAX[x],siz[v]);
}
MAX[x] = Max(MAX[x],S-siz[x]);
if(MAX[x] < MAX[rt] || !rt) rt = x;
}
void predfs(int x,int fa)
{
siz[x] = 1;
for(int i = head[x],v; i ;i = e[i].nxt)
{
if((v = e[i].v) == fa || vis[v]) continue;
predfs(v,x);
siz[x] += siz[v];
}
}
int B[MAXN];
int lowbit(int x){return x & -x;}
void Add(int x,int val){for(int i = x;i <= n;i += lowbit(i)) B[i] += val;}
int Sum(int x){int ret = 0;for(int i = x;i >= 1;i -= lowbit(i)) ret += B[i];return ret;}
int mat,mit;
struct node
{
int x,re;
}ma[MAXN],mi[MAXN];
vector<node> fkma[MAXN],fkmi[MAXN];
void getm(int x,int fa,int MIN,int MAX,int cao)
{
if(x == MIN) mi[++mit] = node{x,MAX},fkmi[cao].emplace_back(node{x,MAX});
if(x == MAX) ma[++mat] = node{x,MIN},fkma[cao].emplace_back(node{x,MIN});
for(int i = head[x],v; i ;i = e[i].nxt)
if(!vis[v = e[i].v] && v != fa)
getm(v,x,Min(MIN,v),Max(MAX,v),cao);
}
void solve(int x)
{
// printf("solve11 %d %lld
",x,ans);
mat = mit = 0;
for(int i = head[x],v; i ;i = e[i].nxt)
if(!vis[v = e[i].v])
getm(v,x,Min(x,v),Max(x,v),v);
for(int i = 1;i <= mit;++ i)
if(mi[i].re == x) ++ans;
for(int i = 1;i <= mat;++ i)
if(ma[i].re == x) ++ans;
if(!mat || !mit)
{
for(int i = head[x],v; i ;i = e[i].nxt)
if(!vis[v = e[i].v])
fkmi[v].clear(),fkma[v].clear();
return;
}
for(int i = head[x],v; i ;i = e[i].nxt)
if(!vis[v = e[i].v])
{
if(!fkmi[v].size() || !fkma[v].size()) continue;
sort(fkma[v].begin(),fkma[v].end(),[](node A,node B){
return A.x < B.x;
});
sort(fkmi[v].begin(),fkmi[v].end(),[](node A,node B){
return A.re < B.re;
});
int now = 0,lenmi = fkmi[v].size();
for(int i = 0,lenma = fkma[v].size();i < lenma;++ i)
{
while(now < lenmi && fkmi[v][now].re < fkma[v][i].x) Add(fkmi[v][now].x,1),++now;
if(now > 0) ans -= Sum(fkma[v][i].re-1);
}
for(int i = 0;i < now;++ i) Add(fkmi[v][i].x,-1);
fkmi[v].clear(); fkma[v].clear();
}
sort(ma,ma+mat+1,[](node A,node B){
return A.x < B.x;
});
sort(mi,mi+mit+1,[](node A,node B){
return A.re < B.re;
});
int now = 1;
for(int i = 1;i <= mat;++ i)
{
while(now <= mit && mi[now].re < ma[i].x) Add(mi[now].x,1),++now;
if(now > 1) ans += Sum(ma[i].re-1);
}
for(int i = 1;i < now;++ i) Add(mi[i].x,-1);
// printf("solve22 %d %lld
",x,ans);
}
void dfs(int x)
{
vis[x] = 1;
predfs(x,0);
solve(x);
for(int i = head[x],v; i ;i = e[i].nxt)
{
if(vis[v = e[i].v]) continue;
rt = 0; getrt(v,x,siz[v]);
dfs(rt);
}
}
int main()
{
freopen("charity.in","r",stdin);
freopen("charity.out","w",stdout);
n = Read(); Read();
for(int i = 2;i <= n;++ i) Add_Double_Edge(Read(),i);
rt = 0; getrt(1,0,n);
dfs(rt);
Put(ans,'
');
return 0;
}
/*
6
0 1 2 2 3 5
12
*/
接下来是正解。
解法很奇妙，我想不到。
考虑路径的最值能想到什么？( t Kruskal) 重构树！这道题是点权，所以我们可以建特殊的重构树。
我们需要建两棵重构树，保证 (lca(x,y)) 是 (x ightarrow y) 路径上的最大值/最小值，这个过程可以用并查集逆序加边实现。
然后我们的问题就转化为有多少个点对在一棵树上是祖先-后代关系而在另一棵树上是后代-祖先关系。
其实也是一个偏序问题，直接树状数组即可。
总时间复杂度 (O(nlog_2n))，常数极小。
代码
经典正解比暴力短
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 2000005;
int n;
LL ans;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[3][MAXN],tot;
struct edge
{
int v,nxt;
}e[MAXN<<2];
void Add_Edge(int opt,int x,int y)
{
e[++tot] = edge{y,head[opt][x]};
head[opt][x] = tot;
}
void Add_Double_Edge(int x,int y)
{
Add_Edge(0,x,y);
Add_Edge(0,y,x);
}
int f[MAXN];
int findSet(int x){if(f[x]^x)f[x]=findSet(f[x]);return f[x];}
int B[MAXN];
int lowbit(int x){return x&-x;}
void Add(int x,int val){for(int i = x;i <= n;i += lowbit(i)) B[i] += val;}
int Sum(int x){int ret = 0;for(int i = x;i >= 1;i -= lowbit(i)) ret += B[i];return ret;}
int dfn[MAXN],dfntot,siz[MAXN];
void dfs1(int x)
{
dfn[x] = ++dfntot; siz[x] = 1;
for(int i = head[1][x]; i ;i = e[i].nxt) dfs1(e[i].v),siz[x] += siz[e[i].v];
}
void dfs2(int x)
{
ans += Sum(dfn[x]+siz[x]-1) - Sum(dfn[x]-1);
Add(dfn[x],1);
for(int i = head[2][x]; i ;i = e[i].nxt) dfs2(e[i].v);
Add(dfn[x],-1);
}
int main()
{
freopen("charity.in","r",stdin);
freopen("charity.out","w",stdout);
n = Read(); Read();
for(int i = 2;i <= n;++ i) Add_Double_Edge(Read(),i);
for(int i = 1;i <= n;++ i) f[i] = i;
for(int x = 1;x <= n;++ x)
for(int i = head[0][x]; i ;i = e[i].nxt)
if(e[i].v < x && (x^findSet(e[i].v)))
Add_Edge(1,x,findSet(e[i].v)),f[findSet(e[i].v)] = x;
for(int i = 1;i <= n;++ i) f[i] = i;
for(int x = n;x >= 1;-- x)
for(int i = head[0][x]; i ;i = e[i].nxt)
if(e[i].v > x && (x^findSet(e[i].v)))
Add_Edge(2,x,findSet(e[i].v)),f[findSet(e[i].v)] = x;
dfs1(n); dfs2(1);
Put(ans,'
');
return 0;
}