【每日一题】Namomo Spring Camp 2022 Div1 #三角果计数

题目链接

给一个 n n n 个节点的树, 三角果定义为一个包含3个节点的集合, 且他们两两之间的最短路长度 a , b , c a, b, c a,b,c 能够构成一个三角形。
计算这棵树上有多少个不同的三角果。

1 ≤ leq ≤ n n n ≤ leq ≤ 1 e 5 1e^5 1e5 , 1 ≤ leq ≤ w_i ≤ leq ≤ 1 0 9 10^9 109

从简单的试试样例可以发现，能否构成三角果是和边权没有关系的，然后就是在一条链上的三个结点都是不行的，其实的结点只要不在一条链上，都是可以被算进答案里面的。
然后我们考虑写一发 d f s dfs dfs 进行求解，以每个点作为中心点，里面的转移方程是不断扩大 s i z [ x ] siz[ x ] siz[x] 从它的孩子结点里面递增过来，然后三个块相乘，累加到答案里面。

当前 x x x 已经访问过 t o 1 , t o 2 to1,to2 to1,to2 了,现在的 s i z [ x ] siz[x] siz[x] 就等于 s i z [ t o 1 ] + s i z [ t o 2 ] siz[to1]+siz[to2] siz[to1]+siz[to2] ,那关于这个状态的转移方程是 a n s + = s i z [ t o 3 ] ∗ s i z [ x ] ∗ ( n − s i z [ t o 3 ] − s i z [ x ] − 1 ) ans+=siz[to3]*siz[x]*(n-siz[to3]-siz[x]-1) ans+=siz[to3]∗siz[x]∗(n−siz[to3]−siz[x]−1)

#include 
using namespace std;
#define int long long
const int maxn=3e5+100;
struct node{
   int to,val;
};
int ans;int n;
vectorg[maxn];
int siz[maxn];
void dfs(int x,int f){
    int len=g[x].size();
    for(int i=0;i>n;
    for(int i=1;i>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1,0);
    cout<