Problem - D1 - Codeforces

這是問題的簡化版本。唯一的區(qū)別在于在該版本中k≤min(n,3)。只有在兩個版本的問題都解決后，才能進(jìn)行黑客攻擊。 琴音和漂浮的島嶼。

洛天依現(xiàn)在生活在一個有n個漂浮島嶼的世界里。這些漂浮島嶼由n?1個無向航線連接，任意兩個島嶼之間都可以通過這些航線到達(dá)。也就是說，這n個漂浮島嶼形成了一棵樹。

有一天，洛天依想見她的朋友：Chtholly、Nephren、William等。她總共想見k個人。她不知道他們的確切位置，但是她知道他們在兩兩不同的島嶼上。她定義一個島嶼是好的，當(dāng)且僅當(dāng)從它到具有k個人的島嶼的距離和為所有n個島嶼中最小的時候。

現(xiàn)在，洛天依想知道，如果將k個人隨機(jī)放置在n個島嶼中的k個不同的島嶼上，那么好的島嶼的期望數(shù)量是多少？你只需要告訴她期望數(shù)量模109+7的值。

?

兩個島嶼之間的距離是你需要采取的最少的航線數(shù)量，以到達(dá)另一個島嶼。 輸入

第一行包含兩個整數(shù)n和k(1≤k≤min(n,3),1≤n≤2?105) - 島嶼和人的數(shù)量。

接下來的n?1行描述了航線。它們中的第i行包含兩個整數(shù)ui和vi(1≤ui,vi≤n,ui≠vi)-第i條空中路線連接的島嶼。 輸出

打印一個整數(shù)-好島嶼的期望數(shù)字模109+7。

嚴(yán)格地說，讓M=109+7。可以證明答案可以表示為不可約分?jǐn)?shù)pq，其中p和q是整數(shù)，q≡?0(modM)。輸出等于p?q?1modM的整數(shù)。換句話說，輸出這樣一個整數(shù)x，使得0≤x<M且x?q≡p(modM)。

Examples

Input

Copy

4 2
1 2
2 3
3 4

Output

Copy

666666674

Input

Copy

5 1
1 2
2 3
3 4
3 5

Output

Copy

1

?題解:

對于k = 1的情況,無論這個點(diǎn)在哪,唯一的好點(diǎn)就是其本身,只有一種可能,所以直接輸出1

對于k = 3的情況,我們可以先確定一個中間的點(diǎn),這個點(diǎn)肯定不能在葉子節(jié)點(diǎn)上,另外兩個點(diǎn)分別放在這個中點(diǎn)兩邊,我們會發(fā)現(xiàn)這樣好點(diǎn)只會是中點(diǎn)本身,也輸出1

對于k = 2的情況,我們可以發(fā)現(xiàn),這兩人在任何兩個不同的點(diǎn)上,好點(diǎn)的數(shù)量是兩個點(diǎn)相連鏈上的點(diǎn)的數(shù)目,我們可以通過單個點(diǎn)對答案的貢獻(xiàn)來求

我們在dfs時可以求所有點(diǎn)的子樹大小,對于這些點(diǎn)對答案的貢獻(xiàn)為,

dp[ne]*(n - dp[ne]),可以理解為右節(jié)點(diǎn)在子樹中,左節(jié)點(diǎn)在子樹外,

?這樣計算完,我們得到的好點(diǎn)數(shù)是10,而答案是16,顯然少了一些貢獻(xiàn),我們多舉幾個例子就能發(fā)現(xiàn),還要加上n*(n - 1)/2,(至于為啥是這樣,想了好長時間,實(shí)在想不明白,望大佬幫忙指正)

最后別忘了除概率n*(n - 1)/2,

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
const int N = 3e5 + 10;
int mod = 1e9 + 7;
vector<int> p[300050];
int ans;
int qpow(int x,int y)
{int ans = 1;while(y){if(y&1)ans = ans*x%mod;x = x*x%mod;y /= 2;} return ans;
}
int m,n;
int dp[N];
void dfs(int x,int fa)
{dp[x] = 1;for(auto ne:p[x]){if(ne == fa)continue;dfs(ne,x);dp[x] = dp[x] + dp[ne];ans = (ans + dp[ne]*(n - dp[ne])%mod)%mod;
//		cout <<ne <<" "<<dp[ne] <<"\n";}
}
void solve()
{int k;cin >> n >> k;for(int i = 1;i < n;i++){int x,y;cin >> x >> y;p[x].push_back(y);p[y].push_back(x);}if(k == 1||k == 3){cout << 1;}else if(k == 2){m = qpow((n*(n - 1)/2)%mod,mod - 2);dfs(1,0);
//		cout << ans ;cout << (ans + (n*(n - 1)/2)%mod)%mod*m%mod;}
}
signed main()
{ios::sync_with_stdio(0 );cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}

?