我必须翻译一下这神人写的题意。

凸包：凸多边形

三角剖分：把这个凸多边形用互不交叉的对角线，分成一个个三角形。 （这里指顶点可以重合，但边不能交叉）

题目要求的：给你凸多边形和它的三角剖分，问有多少条严格不相同的回路？

不想写了看代码注释，wyh 的方法太过于逆天，写不了文字证明。

时间复杂度：dfs 时候每个顶点被调用的次数等于其入度，而总入度 = 总边数 = $O(N)$。

所以瓶颈居然在排序 $O(NlogN)$。

这集神了。

// 代码 & 做法 by wyh
// 注释 by proMatheus，包含个人理解

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL P = 1e9 + 7;
const int N = 2e5 + 10;

LL ans;                     // 最终答案（本质不同的回路总数）
vector<int> G[N];      // 邻接表只存储从编号小指向编号大的边

// 实际上就是取不重复的三元组 (x, y, z)，连成一个“三角形”
// 有几个三角形就是有几个回路
// 为了三元组的严格不同，我们强制要求 x < y < z
// 同时保证 x 是有边直接指向 y 的，z 则是该回路中编号最大的点
// 因此我们将点按编号小指向编号大连边
// 可以保证所有可能的回路都能唯一构成一个这样的三元组

// 还有一个点，题目保证对角线不相交
// 这样也是方便求回路时遍历的点一定是从小到大

LL dfs(int x) {
    LL w = 0;
    for (int y : G[x]) if (y != G[x].back()) {
        // 这里 x 作为第一个点，y 及 y 前面与 x 相连的点作为第二个点（的人选）
        // 让 y 去寻找有多少个第三个点符合的人选
        // 那就有可爱的小朋友要问了：
        // 为什么不遍历 x 连的最大的点呢？
        // 还有为什么找不到点也会返回 1 呢？
        // 你可以当作这些找不到的点返回 1，就是和那个最大的点配对
        // 而且，x 能连到最大的点，如果它作为第二个点
        // 我们无法找到比它大的点，还能走回 x
        // 因为走边是严格按照从小到大走的
        w ++;                               
        w = (w * dfs(y)) % P; 
        ans = (ans + w) % P;       
    }
    return (w + 1) % P; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; i ++) {
        G[i].push_back(i + 1);
    }
    
    G[1].push_back(n);
    // 1 和 n 之间也是严格从小到大
    // 同时，n 作为 1 能连到最大的点
    // 它更没有招数再找一个更大的点作为第三个点

    for (int i = 1; i <= n - 3; i ++) {
        int x, y;
        cin >> x >> y;
        if (x > y) {
            swap(x, y);
        }
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end());
        // 必须给每个连到的点排序
        // 我们必须保证在当前点的下一层按顺序遍历
        // 这样才好统计三元组
    }

    LL t = dfs(1);

    cout << ans << "\n";
    return 0;
}

三角剖分一定由一个外部环（凸包），加上 $n-3$ 条内部连边构成。容易看出它一定被划分成 $n-2$ 个三角形。

对于简单回路计数，由于是简单回路，手玩一下可以得到结论：三角剖分的回路数量，就等于这 $n-2$ 个三角形构成的凸多边形数量。

考虑将 $n-2$ 个三角形看成 $n-2$ 个点，相邻三角形连边，那么就变成了树上连通块计数。建树过程可以参考代码实现。

我们假定：一个树上连通块的根，是连通块内深度最小的节点。用 $dp_i$ 表示以 $i$ 为根的连通块个数，有转移方程 $dp_u=\prod\limits_{v\in son_u}(dp_v+1)$。答案是 $\sum dp_u$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5,M=1e9+7;
int n,dp[N],rs;
struct node{
    int u,v,i;
    bool operator<(node x)const{
        return u==x.u?v<x.v:u<x.u;
    }
}a[N];
set<node>st;
vector<int>e[N];
void dfs(int u,int fa){
    dp[u]=1;
    for (auto v:e[u]){
        if (v==fa)
            continue;
        dfs(v,u);
        dp[u]=dp[u]*(dp[v]+1)%M;
    }
    (rs+=dp[u])%=M;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    fo(i,1,n-3){
        int u,v;
        cin>>u>>v;
        if (u>v)
            swap(u,v);
        a[i]={u,v,i};
    }
    sort(a+1,a+n-2,
        [](const node x,const node y){
            return x.v-x.u<y.v-y.u;
        }
    );
    fo(i,1,n-3){
        set<node>::iterator it=st.lower_bound({a[i].u,0,0});
        while (it!=st.end()&&(*it).u<a[i].v){
            e[a[i].i].push_back((*it).i);
            e[(*it).i].push_back(a[i].i);
            it=st.erase(it);
        }
        st.insert(a[i]);
    }
    for (auto i:st){
        e[n-2].push_back(i.i);
        e[i.i].push_back(n-2);
    }
    dfs(1,0);
    cout<<rs<<'\n';
    return 0;
}
``