「SWTR-8」地地铁铁

Luogu

IDLGP8456

Time2000ms

Memory512MB

DifficultyP6

洛谷原创O2优化洛谷月赛圆方树

给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。注意： - 简单路径定义为不经过重复 **节点** 的路径。 - 保证图无自环，可能有重边。 ## Input 第一行一个整数 $S$，表示该测试点的 Subtask 编号。第二行两个整数 $n, m$。接下来 $m$ 行，每行两个整数 $x, y$ 以及字母 $c$，表示一条连接 $x, y$ 且标有 $c$ 的无向边。 ## Output 一行一个整数表示答案。 [samples] ## Background D_T_ : D_tt : ddT_ : ddtt = 9 : 3 : 3 : 1. ## Note **「数据范围与约定」** **本题采用捆绑测试**。 - Subtask #1（6 points）：$n \leq 8$，$m \leq 20$。 - Subtask #2（16 points）：$n\leq 15$，$m\leq 822$。依赖 Subtask #1。 - Subtask #3（17 points）：$m = n - 1$。 - Subtask #4（18 points）：$m = n$。 - Subtask #5（19 points）：$n\leq 1064$，$m\leq 10 ^ 4$。依赖 Subtask #2。 - Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。对于 $100\%$ 的数据： - $2\leq n \leq 4\times 10 ^ 5$，$n - 1\leq m\leq 10 ^ 6$。 - $1\leq x, y\leq n$。 - $c\in \{\texttt{D}, \texttt{d}\}$。 - 保证图无自环，可能有重边。 **「帮助与提示」** 请注意 IO 优化。 **「题目来源」** - [Sweet Round 8](https://www.luogu.com.cn/contest/73382) E - Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。 - Tester：[asmend](https://www.luogu.com.cn/user/21658)。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「SWTR-8」地地铁铁",
    "description": {
      "content": "给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。 定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \\neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。 小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。 注意： - 简单路径定义为不经过重复",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8456"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。\n\n定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \\neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。\n\n小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。\n\n注意：\n\n- 简单路径定义为不经过重复...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments