CF1156D 0-1-Tree 换根DP

本文主要是介绍CF1156D 0-1-Tree 换根DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考 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;elsef[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;
}

 

这篇关于CF1156D 0-1-Tree 换根DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---