HDU 4705 Y (樹形DP+計數)*

Y

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 2865    Accepted Submission(s): 835

Problem Description

Sample Input

4 1 2 1 3 1 4

Sample Output

1

Hint

1. The only set is {2,3,4}. 2. Please use #pragma comment(linker, "/STACK:16777216")

Source

2013 Multi-University Training Contest 10

Recommend

zhuyuanchen520   |   We have carefully selected several similar problems for you:  6437 6436 6435 6434 6433 

#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
ll gcd(ll x,ll y)  {  return y==0?x:gcd(y,x%y); }
const int  maxn =1e5+5;
const int mod=1e9+7;
/*
題目大意:找出樹中三點對對數，
滿足一條簡單路徑不覆寫這三點對。

這道題明顯的樹形DP計數的味道在裡面，
正難則反，我在思考找符合題意的三點對時也是踩了不少坑，
主要打破我幻想的一個例子就是，可以存在兩個點在一個子樹中， 
另一個點在子樹外面的情況，這樣我的想法就有漏洞。

正難則反，我們考慮一條路徑能覆寫的三點對，a,b,c,
在周遊根節點時，假設一個節點在根節點上，另一個點在目前枚舉的子樹中，
那麼如何完全不重複的統計這類情況的個數呢？
在更新sons[u]的過程中，sons[u]同時也是子樹節點數量的字首和，
是以用總結點數減去該字首和就得到未和目前子樹配對的節點數量，
注意這裡并沒有重複計算，因為之前計算過的肯定不會與目前節點配對，
在總數中已經減去了。


*/

int n,x,y;
///鍊式前向星
struct node
{
    int u,nxt;
};
node edge[maxn<<2];
int head[maxn],tot=0;
void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}
void add(int x,int y)
{
    edge[tot]=node{y,head[x]};
    head[x]=tot++;
}

ll ans,sons[maxn];///計數

void dfs(int u,int pre,int dis)
{
    sons[u]=1;
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v=edge[i].u;
        if(v==pre) continue;

        dfs(v,u,dis+1);

        sons[u]+=sons[v];
        ans+=1LL*(n-sons[u])*sons[v];
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }

        ans=0;
        memset(sons,0,sizeof(sons));

        dfs(1,-1,0);

        ll tot=1LL*n*(n-1)*(n-2)/6;

        printf("%lld\n",tot-ans);
    }
    return 0;
}
/*
6
1 2
1 3
3 4
3 5
1 6

4 6
4 7
5 8
5 9


*/