HDU 4705 Y - dblank

HDU 4705 Y

hdu 4705 Y

题意:给出一颗树,有多少三个点的点集,这三个点不在同一路径上。

思路:我们可以用总共的C(n,3)减去在一条路径上的的点集数。我们可以枚举同一路径三点中的中间点,然后就是这个中间点的子树节点总数*(节点总数减去以该点为根节点的节点个数)。我们可以用树形dp来统计。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 400000 + 10, Mod = 1000000000;
typedef long long ll;
struct node
{
    int next, to;
} path[N];
int vis[N], head[N], son[N], cnt, n;
ll ans;
void add(int u, int v)
{
    path[cnt].to = v;
    path[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int cur)
{
    vis[cur] = 1;
    int tmp  = 0;
    for(int i = head[cur]; ~i; i = path[i].next)
    {
        int u = path[i].to;
        if(!vis[u])
        {
            dfs(u);
            son[cur] += son[u] + 1;
            ans += (ll)(n-son[cur]-1)*(son[u]+1);
        }
    }
}
int main()
{
    int t, u, v;
    while(~scanf("%d", &n))
    {
        ans = 0;
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        memset(head, -1, sizeof(head));
        memset(son, 0, sizeof(son));
        for(int i = 1; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dfs(1);
        ll tot = (ll)n(n-1)(n-2)/6;
        printf("%I64dn", tot - ans);
    }
    return 0;
}  

 

相关文章

发表新评论