#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200010
#define inf 1000000007
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[maxn];
int col[maxn],fa[maxn],size[maxn];
int d[7][maxn];
int n;
int head[maxn],nxt[maxn*2],to[maxn*2],tot;
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
ll ans=0;
void dfs1(int x,int las)
{
    fa[x]=las;size[x]=col[x];
    if(!nxt[head[x]]&&x!=1)
    {
        d[1][x]=0;
        if(col[x])  d[3][x]=0;
        else        d[3][x]=inf;
        return;
    }
    int mx=0,mx2=inf;
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        int v=to[i];
        dfs1(v,x);
        size[x]+=size[v];
        mx=max(mx,d[1][v]);
        if(d[3][v]<inf)  mx2=min(mx2,d[1][v]);
    }
    d[1][x]=mx+1;d[3][x]=mx2+1;
    if(col[x])  d[3][x]=min(d[3][x],d[1][x]);
}
int p[maxn],top;
int pre[maxn],suf[maxn];
void dfs2(int x,int las)
{
    d[2][x]=max(d[2][x],(las!=0)+d[2][las]);
    if(las)  d[5][x]=max(d[5][x],d[2][x]-1);
    top=0;
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        p[++top]=to[i];
    }
    pre[0]=suf[top+1]=-1;
    for(int i=1;i<=top;i++)  pre[i]=max(pre[i-1],d[1][p[i]]);
    for(int i=top;i>=1;i--)  suf[i]=max(suf[i+1],d[1][p[i]]);
    for(int i=1;i<=top;i++)  d[2][p[i]]=max(d[2][p[i]],max(pre[i-1],suf[i+1])+2);
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        dfs2(to[i],x);
    }
}
int main()
{
    n=read();
    memset(d[3],125,sizeof(d[3]));
    memset(d[4],125,sizeof(d[4]));
    for(int i=1;i<n;i++)
    {
        int q=read(),w=read();
        add(q,w);
        add(w,q);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)  col[i]=s[i]-'0';
    int flag=0;
    for(int i=1;i<=n;i++)  flag|=col[i];
    if(!flag)
    {
        puts("0");
        return 0;
    }
    if(n==1)
    {
        puts("1");
        return 0;
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        if(col[i])  d[6][i]=0;
        else        d[6][i]=min(d[3][i],(size[i]==size[1])?inf:d[2][i]);
        int tmp=max(d[1][i],d[2][i])-1;
        for(int j=head[i];j;j=nxt[j])
        {
            int v=to[j];
            if(v==fa[i])  tmp=min(tmp,d[1][i]+1);
            else          tmp=min(tmp,d[5][v]+1);
        }
        ans+=max(tmp-d[6][i]+1,0);
    }
    cout<<ans+1<<endl;
    return 0;
}
### Prompt

In cpp, your task is to solve the following problem:

There is a tree with N vertices. The vertices are numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i. The lengths of all the edges are 1.

Snuke likes some of the vertices. The information on his favorite vertices are given to you as a string s of length N. For each 1 ≤ i ≤ N, s_i is `1` if Snuke likes vertex i, and `0` if he does not like vertex i.

Initially, all the vertices are white. Snuke will perform the following operation exactly once:

* Select a vertex v that he likes, and a non-negative integer d. Then, paint all the vertices black whose distances from v are at most d.



Find the number of the possible combinations of colors of the vertices after the operation.

Constraints

* 2 ≤ N ≤ 2×10^5
* 1 ≤ a_i, b_i ≤ N
* The given graph is a tree.
* |s| = N
* s consists of `0` and `1`.
* s contains at least one occurrence of `1`.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s


Output

Print the number of the possible combinations of colors of the vertices after the operation.

Examples

Input

4
1 2
1 3
1 4
1100


Output

4


Input

5
1 2
1 3
1 4
4 5
11111


Output

11


Input

6
1 2
1 3
1 4
2 5
2 6
100011


Output

8

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200010
#define inf 1000000007
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[maxn];
int col[maxn],fa[maxn],size[maxn];
int d[7][maxn];
int n;
int head[maxn],nxt[maxn*2],to[maxn*2],tot;
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
ll ans=0;
void dfs1(int x,int las)
{
    fa[x]=las;size[x]=col[x];
    if(!nxt[head[x]]&&x!=1)
    {
        d[1][x]=0;
        if(col[x])  d[3][x]=0;
        else        d[3][x]=inf;
        return;
    }
    int mx=0,mx2=inf;
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        int v=to[i];
        dfs1(v,x);
        size[x]+=size[v];
        mx=max(mx,d[1][v]);
        if(d[3][v]<inf)  mx2=min(mx2,d[1][v]);
    }
    d[1][x]=mx+1;d[3][x]=mx2+1;
    if(col[x])  d[3][x]=min(d[3][x],d[1][x]);
}
int p[maxn],top;
int pre[maxn],suf[maxn];
void dfs2(int x,int las)
{
    d[2][x]=max(d[2][x],(las!=0)+d[2][las]);
    if(las)  d[5][x]=max(d[5][x],d[2][x]-1);
    top=0;
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        p[++top]=to[i];
    }
    pre[0]=suf[top+1]=-1;
    for(int i=1;i<=top;i++)  pre[i]=max(pre[i-1],d[1][p[i]]);
    for(int i=top;i>=1;i--)  suf[i]=max(suf[i+1],d[1][p[i]]);
    for(int i=1;i<=top;i++)  d[2][p[i]]=max(d[2][p[i]],max(pre[i-1],suf[i+1])+2);
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==las)  continue;
        dfs2(to[i],x);
    }
}
int main()
{
    n=read();
    memset(d[3],125,sizeof(d[3]));
    memset(d[4],125,sizeof(d[4]));
    for(int i=1;i<n;i++)
    {
        int q=read(),w=read();
        add(q,w);
        add(w,q);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)  col[i]=s[i]-'0';
    int flag=0;
    for(int i=1;i<=n;i++)  flag|=col[i];
    if(!flag)
    {
        puts("0");
        return 0;
    }
    if(n==1)
    {
        puts("1");
        return 0;
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        if(col[i])  d[6][i]=0;
        else        d[6][i]=min(d[3][i],(size[i]==size[1])?inf:d[2][i]);
        int tmp=max(d[1][i],d[2][i])-1;
        for(int j=head[i];j;j=nxt[j])
        {
            int v=to[j];
            if(v==fa[i])  tmp=min(tmp,d[1][i]+1);
            else          tmp=min(tmp,d[5][v]+1);
        }
        ans+=max(tmp-d[6][i]+1,0);
    }
    cout<<ans+1<<endl;
    return 0;
}
```