sone3 - Problem

#1491. sone3

Statistics

给定一颗 $n$ 个结点的树，每条边上有一个小写字母。

令 $str(x,y)$ 表示树上 $x$ 到 $y$ 的简单路径上的字母连成的字符串。

定义一个字符串 $T$ 是优秀的，当且仅当 $T$ 能表示成 $SS$ 的形式，其中 $S$ 是一个任意非空字符串。

求树上有多少个本质不同的优秀字符串。

输入格式

输入第一行一个正整数 $n$（$2 \leq n \leq 5 \times 10^4$），表示树的大小。

接下来 $n-1$ 行，每行形如 $x,y,c$ 表示有一条连接 $(x,y)$ 的边，上面的小写字母是 $c$。

输出格式

输出一个非负整数表示答案

样例一

input

output

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0