題目鏈接：點(diǎn)擊查看

題目大意：給出一棵樹，求三個(gè)點(diǎn)不在一條線上的個(gè)數(shù)

題目分析：正難取反，正著求不管是暴力還是有點(diǎn)技巧都是實(shí)現(xiàn)不了的，我們可以求出來三個(gè)點(diǎn)在一條直線上的方案數(shù)，然后用總的排列組合的方案減去三個(gè)點(diǎn)在一條直線的方案數(shù)，就是最終答案了，那么該怎么求三個(gè)點(diǎn)在一條直線上的數(shù)量呢？我們可以利用樹形dp，期間維護(hù)子樹中節(jié)點(diǎn)的數(shù)量，每次選擇子樹的根節(jié)點(diǎn)作為直線上三個(gè)點(diǎn)的那個(gè)中點(diǎn)，然后從子樹中選擇任意一點(diǎn)，再從剩下的點(diǎn)中（即n-sum[v]-1個(gè)點(diǎn)）選擇任意一點(diǎn)，這樣的組合數(shù)記得要注意不要加重復(fù)了，解決方法就是開一個(gè)temp變量用來記錄當(dāng)前根節(jié)點(diǎn)下已經(jīng)統(tǒng)計(jì)過的子樹的數(shù)量，然后求“剩下的點(diǎn)”這個(gè)值的時(shí)候就不會(huì)把先前已經(jīng)記錄過的子樹再計(jì)算一遍了，詳細(xì)的請見代碼中的dfs函數(shù)的書寫法

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e5+100;vector<int>node[N];int num[N];LL sum;LL n;void dfs(int u,int fa) {LL temp=0;//用來保存已經(jīng)用過的節(jié)點(diǎn)for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs(v,u);num[u]+=num[v];temp+=num[v];sum+=num[v]*(n-temp-1);//在這里計(jì)算組合數(shù)時(shí)，記錄的是該子樹的數(shù)量乘以還沒有用過的節(jié)點(diǎn)，而不是除了該子樹之外的所有點(diǎn)} }int main() { // freopen("input.txt","r",stdin)while(scanf("%lld",&n)!=EOF){for(int i=1;i<=n;i++){node[i].clear();num[i]=1;}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}sum=0;dfs(1,-1);LL totle=n*(n-1)*(n-2)/6;//排列組合cout<<totle-sum<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4705 Y(树形dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。