一、题意回顾（精简版）

给定一棵 $n$ 个节点的树。 对所有有序对 $(p,q)$，$p\neq q$，两人进行博弈：

• Nora 先手，只能从 $p$ 向外扩展毛虫；
• Aron 后手，只能从 $q$ 向外扩展毛虫；
• 若 $p$ 是叶子，Nora 胜；
• 若 $q$ 是叶子，Aron 胜；
• 初始两者都是叶子，或 $10^{100}$ 轮未分胜负，则平局。

求：使得 Aron 必胜的有序对 $(p,q)$ 数量。

---

二、结论性转化（本题核心）

通过博弈分析与树上结构观察，可以得出：

Aron 获胜的充要条件

满足下列两类之一：

1. 初始直接获胜 $q$ 是叶子，且 $p$ 不是叶子。

2. 博弈后获胜 满足：

   • $p$ 不是叶子；
   • $q$ 不是叶子；
   • $q$ 是全内部点（所有邻居都不是叶子）；
   • $p$ 是非全内部点（至少有一个邻居是叶子）。

---

三、定义与符号

为方便表述，统一符号：

• $\deg(u)$：节点 $u$ 的度数

• 叶子：$\deg(u)=1$，记叶子集合为 $L$ 数量：$c_1=|L|$

• 内部点：$\deg(u)\ge 2$

对内部点 $u$，定义：

• $d(u)$：$u$ 的邻居中也是内部点的数量

• 全内部点（记为集合 $S$）： 满足 $d(u)=\deg(u)$，即所有邻居都是内部点 数量：$c_2=|S|$

• 非全内部点（记为集合 $T$）： 内部点但 $d(u)<\deg(u)$，即至少一个邻居是叶子

---

四、答案公式

最终答案由两部分相加：

[ \mathrm{ans}=c_1\cdot(n-c_1);+;c_2\cdot\sum_{m\in T}\big(d(m)-1\big) ]

逐项解释：

1. 第一部分 [ c_1 \cdot (n - c_1) ]

• $c_1$：叶子 $q$ 的数量
• $n-c_1$：非叶子 $p$ 的数量
• 含义：所有满足 $q$ 是叶子，$p$ 不是叶子 的有序对，Aron 直接获胜。

2. 第二部分 [ c_2 \cdot \sum_{m\in T}\big(d(m)-1\big) ]

• $c_2$：全内部点 $q$ 的数量
• 对每个非全内部点 $m$（作为 $p$），贡献为 $d(m)-1$
• 含义：博弈后 Aron 能必胜的有序对数量。

---

五、标程逐段解释

1. 基础预处理

int n; cin >> n;
for (int i=1;i<n;++i) {
    int u,v; cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
}

读入树，建邻接表。

---

2. 统计叶子数量 $c_1$

int c1=0;
for(int i=1;i<=n;++i)
    c1 += (deg(i)==1);

• $\deg(i)=1$ 是叶子
• $c_1=|L|$

然后计算第一部分答案：

ans += 1LL * c1 * (n - c1);

---

3. 统计 $d(u)$ 与全内部点数量 $c_2$

for(int i=1;i<=n;++i)
if(deg(i)>1){
    for(int v:g[i])
        d[i] += (deg(v)>1);
    c2 += (d[i]==deg(i));
}

• 只对内部点计算
• $d[i]$：邻居中内部点个数
• 若 $d[i]=\deg(i)$，则 $i\in S$，$c_2$ 加一

---

4. 计算第二部分答案

for(int m=1;m<=n;++m)
if(deg(m)>1 && d[m]!=deg(m))
    ans += 1LL * c2 * (d[m]-1);

• 遍历所有非全内部点 $m$
• 每个贡献 $d[m]-1$
• 乘上全内部点数量 $c_2$

---

六、复杂度分析

• 建树：$O(n)$
• 遍历统计度数、$d(u)$：$O(n)$
• 每组测试用例总复杂度：$O(n)$

满足约束：

• $t\le 2\cdot 10^4$
• $\sum n \le 4\cdot 10^5$

---

七、样例验证（第二个样例）

输入：

5
1 2
1 3
2 4
2 5

节点度数：

• $\deg(1)=2,\ \deg(2)=3$
• $\deg(3)=\deg(4)=\deg(5)=1$

因此：

• 叶子：$3,4,5\Rightarrow c_1=3$
• 非叶子：$1,2\Rightarrow n-c_1=2$
• 第一部分：$3\times 2=6$

内部点：$1,2$

• $d(1)$：邻居只有 $2$（内部点）$\Rightarrow d(1)=2=\deg(1)\Rightarrow$ 全内部点
• $d(2)$：邻居 $1$（内部）、$4$（叶）、$5$（叶）$\Rightarrow d(2)=1<3$
• $c_2=1$

非全内部点只有 $2$，贡献 $d(2)-1=0$ 第二部分：$1\times 0=0$

总答案：$6+0=6$ 与样例输出一致。

---

八、总结

本题表面是复杂树上博弈，实际结论非常简洁：

[ \boxed{\mathrm{ans}=c_1(n-c_1);+;c_2\sum_{m\in T}\big(d(m)-1\big)} ]

标程正是严格按照该公式线性计算，时间效率最优、代码极简洁。