Aiiage Camp Day6 A Line Graph

题意

　　定义Line Graph L(G)为：每个点对应G中的一条边，两点间有边当且仅当在G中两边共点。

　　给出一棵树，问有多少连通子图满足L(L(L(L(...L(G)...)(10^100个L)和L(L(L(L(...L(G)...)(10^100 + 1个L)同构。

　　1<=n<=100000

题解

　　同构要求在L(G)=G时才成立。

　　满足L(G)=G的图有且仅有三角形。

　　在树中，3个叶子的菊花树可以通过一次L操作变成三角形。

　　所以只需要找出所有度数大于3的点，每个点提供的方案数为C(度数，3)。

 1 #include <bits/stdc++.h>
 2 #define MOD (1000000007)
 3 using namespace std;
 4 
 5 int d[100010];
 6 long long jc[100010];
 7 
 8 long long inv(long long t, long long p)
 9 {
10     return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
11 }
12 
13 int C(int n, int m)
14 {
15     return (jc[n] * inv((jc[m] * jc[n - m]) % MOD, MOD)) % MOD;
16 }
17 
18 int main()
19 {
20     jc[0] = 1;
21     for (int i = 1; i <= 100000; ++i)
22         jc[i] = (1ll * jc[i - 1] * i) % MOD;
23     int n;
24     scanf("%d", &n);
25     for (int i = 1; i < n; ++i)
26     {
27         int u, v;
28         scanf("%d%d", &u, &v);
29         d[u]++;
30         d[v]++;
31     }
32     long long ans = (1ll * (n + 1) * n / 2) % MOD;
33     for (int i = 1; i <= n; ++i)
34         if (d[i] >= 3)
35             ans = (ans + C(d[i], 3)) % MOD;
36     printf("%lld
", ans);
37     
38     return 0;
39 }