B-jiege's tree (pressed tree DP)

link ： Jack's tree

The question ：

Given a tree , Border right yes These six characters , Find different path numbers , The characters on the path are required to appear exactly an even number of times .

practice ：

Only care about parity , Then a character can have two states ——1 Represents an odd number of ,0 Represents an even number of , To indicate whether six characters are odd or even at the same time , You can use 0~63 To express .

Definition In order to A node is the starting point , Status as How many paths are there , If My son is , The current character is , that , Except for the transfer from the son's state , There will be a new state , The state of not inheriting a son , To This side of can also be used as a state alone , Then when when , .

There are also some considerations As an intermediate node , This simple , from Calculation is enough .

Code ：

struct tree
{
    int y, val;
};
vector<tree> v[N];
int f[N][1ll << 6];
int ans;
void dfs(int x, int fa)
{
    f[x][0] = 0;
    for (auto tt : v[x])
    {
        int y = tt.y, val = tt.val;
        if (y == fa) continue;
        dfs(y, x);
        for (int i = 0; i < (1ll << 6); i++)
        {
            f[x][i] += f[y][i ^ (1ll << val)];
            if (i == (1ll << val)) f[x][i]++;   // Don't add 1, The reason to add 1, Because of the definition x This point has only one side 
        }
    }
    ans += f[x][0];
    int sum = 0;
    for (auto tt : v[x])
    {
        int y = tt.y, val = tt.val;
        if (y == fa) continue;
        for (int i = 0; i < (1ll << 6); i++)
        {
            int x1 = f[x][i] - f[y][i ^ (1ll << val)] - (i == (1ll << val));
            int x2 = f[y][i ^ (1ll << val)] + (i == (1ll << val));
            sum += x1 * x2;
        }
    }
    ans += sum / 2;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        char c;
        scanf("%lld%lld", &x, &y);
        cin >> c;
        v[x].emplace_back(tree{y, c - 'a'});
        v[y].emplace_back(tree{x, c - 'a'});
    }
    dfs(1, 0);
    cout << ans << "\n";
}