参考 https://www.luogu.org/problemnew/solution/CF1156D

D. 0-1-Tree

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a tree (an undirected connected acyclic graph) consisting of nn vertices and n−1n−1 edges. A number is written on each edge, each number is either 00 (let's call such edges 00 -edges) or 11 (those are 11 -edges).

Let's call an ordered pair of vertices (x,y)(x,y) (x≠yx≠y ) valid if, while traversing the simple path from xx to yy , we never go through a 00 -edge after going through a 11 -edge. Your task is to calculate the number of valid pairs in the tree.

Input

The first line contains one integer nn (2≤n≤2000002≤n≤200000 ) — the number of vertices in the tree.

Then n−1n−1 lines follow, each denoting an edge of the tree. Each edge is represented by three integers xixi , yiyi and cici (1≤xi,yi≤n1≤xi,yi≤n , 0≤ci≤10≤ci≤1 , xi≠yixi≠yi ) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

Output

Print one integer — the number of valid pairs of vertices.

Example

Input

Copy

7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1

Output

Copy

34

Note

The picture corresponding to the first example:

很容易想到一个DP，令f[i]表示以i为根的子树，从下面的节点走上来，最后一步是黑边的点数，g[i]表示全走白边的点数，于是就有f[u]=Σ(f[son]+g[son]+1)，son为经过黑边的son，g[u]=Σ(g[son]+1)，son为经过白边的son。然后这个东西很容易换根DP，根据黑白边讨论一下即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
int n,cnt,f[N],g[N],nf[N],ng[N],hd[N],v[N<<1],nxt[N<<1],w[N<<1];
ll ans;
void adde(int x,int y,int z){v[++cnt]=y,nxt[cnt]=hd[x],w[cnt]=z,hd[x]=cnt;}
void dfs(int u,int fa)
{
    for(int i=hd[u];i;i=nxt[i])
    if(v[i]!=fa)
    {
        dfs(v[i],u);
        if(!w[i])
            g[u]+=g[v[i]]+1;
        else
        f[u]+=f[v[i]]+g[v[i]]+1;
    }
}
void dfs2(int u,int fa)
{
    ans+=nf[u]+ng[u];
    for(int i=hd[u];i;i=nxt[i])
    if(v[i]!=fa)
    {
        if(!w[i])nf[v[i]]=f[v[i]],ng[v[i]]=ng[u];
        else nf[v[i]]=nf[u]-g[v[i]]+ng[u],ng[v[i]]=g[v[i]];
        dfs2(v[i],u);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),adde(x,y,z),adde(y,x,z);
    dfs(1,0);
    nf[1]=f[1],ng[1]=g[1],dfs2(1,0);
    cout<<ans;
}