hdu4705(樹形DP)

Y

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

Total Submission(s): 128    Accepted Submission(s): 41

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  

本題要求不存在歐拉路徑的3的點的組合數。如果僅從排列組合的角度，本題是不好解的，可以換種求補的思想。正難則反。

所求=總的組合數-存在歐拉路徑的3的點的組合數。由于本題是圖，是以可以考慮在周遊的過程中求解。題目提示棧，是以用DFS。

若周遊到某一節點u，某時刻假設以u為根節點的已經周遊過的子孫節點的數目為tmp,我們正DFS u的一顆子樹v（num[v]），則此時新加的存在歐拉路徑的3的點的組合數為tmp*num[v],tmp+=num[v],即與v不同一分支的任一結點，u和分支v上的任一節點三者肯定存在歐拉路徑。此外以u為根節點的任一結點、u和樹上的不在u這棵子樹的其他任一節點都可組成歐拉路徑，于是又新添tmp*(n-num[u]).

#include<iostream>
#include<cstring>
#include<cstdio>
#pragma comment(linker, "/STACK:16777216")
using namespace std;

//***************************************************
const int MAXN=100000+100;//定義頂點個數
struct Node
{
    int to;
    int next;
}edge[MAXN*2];//存放邊資訊，鄰接表的邊最多為2倍的頂點數
int head[MAXN];//存放節點資訊，鄰接表的簡易實作方案
int tol,n;
void add(int a,int b)
//建立a->b的有向邊函數
{
    edge[tol].to=b;
    edge[tol].next=head[a];
    head[a]=tol++;
}
void init()
//初始化函數
{
    tol=0;//頂點個數
    memset(head,-1,sizeof(head));//初始化頭頂點都無邊
}
//***************************************************
__int64 op_ans;
__int64 num[MAXN];
void DFS(int cur,int pre)
{
	int i;
	num[cur]=1;
	__int64 tmp=0;
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int u=edge[i].to;
		if(u==pre)continue;
		DFS(u,cur);
		op_ans+=tmp*num[u];
		tmp+=num[u];
		num[cur]+=num[u];
	}
	op_ans+=tmp*((__int64)n-num[cur]);
}

int main()
{
	int i,s,e;
	while(~scanf("%d",&n))
	{
		init();
		for(i=0;i<n-1;i++)
		{
			scanf("%d%d",&s,&e);
			add(s,e);
			add(e,s);
		}
		op_ans=0;
		DFS(2,-1);
		printf("%I64d\n",(__int64)n*(n-1)*(n-2)/6-op_ans);
	}
	return 0;
}