# 【CodeChef PRIMEDST】Prime Distance On Tree

### 解题报告

$$\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}$$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 66000;
const int M = 110000;
const int INF = 1e9;
const double EPS = 1e-2;
const double PI = acos(-1);

LL vout;

inline void Add_Edge(int u, int v) {
static int T = 0;
}

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Fast_Fourier_Transform{
typedef complex<double> E;
complex<double> a[N<<1];
int pri[M],vis[M],pos[N<<1],tot,len,stp;
public:
Fast_Fourier_Transform() {
for (int i=2;i<M;i++) {
if (!vis[i]) pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<M;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j] == 0) break;
}
}
}
inline LL solve(int t, int *arr) {
for (len=1,stp=-1;len<=t*2;len<<=1,++stp);
memset(a,0,sizeof(E)*(len+9));
for (int i=0;i<=t;i++)
a[i].real() = arr[i];
for (int i=1;i<len;i++) {
pos[i] = pos[i>>1] >> 1;
if (i & 1) pos[i] |= 1 << stp;
}

fft(a, 1);
for (int i=0;i<len;i++)
a[i] *= a[i];
fft(a, -1);
LL ret = 0;
for (int i=1;i<=tot&&pri[i]<=t*2;i++)
ret += a[pri[i]].real() / len + EPS;
return ret;
}
private:
inline void fft(E *arr, int t) {
for (int i=0;i<len;i++)
if (pos[i] < i) swap(arr[pos[i]], arr[i]);
for (int k=0,gap=2;k<=stp;k++,gap<<=1) {
E wn(cos(2*PI/gap),t*sin(2*PI/gap));
for (int j=0;j<len;j+=gap) {
complex<double> cur(1, 0),t1,t2;
for (int i=j;i<j+gap/2;i++,cur*=wn) {
t1 = arr[i]; t2 = cur * arr[i+gap/2];
arr[i] = t1 + t2;
arr[i+gap/2] = t1 - t2;
}
}
}
}
}FFT;

class Node_Based_Divide_and_Conquer{
int area_size,cur_ans,root,tot;
int sum[N],vis[N],cnt[N];
public:
inline void solve() {
area_size = n; cur_ans = INF;
Get_Root(1, 1);
work(root, area_size);
}
private:
void work(int w, int sz) {
vis[w] = 1;
vout += solve(w, 0);
if (!vis[to[i]]) {
vout -= solve(to[i], 1);
area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
cur_ans = INF; Get_Root(to[i], w);
work(root, area_size);
}
}
}
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, area_size - sum[w]);
if (mx < cur_ans) {
cur_ans = mx;
root = w;
}
}
LL solve(int w, int bas) {
memset(cnt,0,sizeof(int)*(tot+9));
tot = 0; Get_Dis(w, bas, w);
return FFT.solve(tot, cnt);
}
void Get_Dis(int w, int d, int f) {
cnt[d]++;
tot = max(tot, d);
if (to[i] != f && !vis[to[i]])
Get_Dis(to[i], d+1, w);
}
}NDC;

int main() {
for (int i=1;i<n;i++)
NDC.solve();
printf("%.10lf\n",(double)vout/n/(n-1));
return 0;
}


## 23 thoughts to “【CodeChef PRIMEDST】Prime Distance On Tree”

1. It’s genuinely very difficult in this full of activity life to listen news on Television, so I
only use web for that purpose, and obtain the latest information.

2. I quite like reading through a post that will make people think.
Also, many thanks for allowing for me to comment!

3. Thank you a bunch for sharing this with all of
us you really understand what you’re talking approximately!
agreement among us

4. After exploring a number of the blog posts on your
to my bookmark site list and will be checking back in the
near future. Take a look at my website as well and tell me
what you think.

5. I’m gone to inform my little brother, that he should also pay a visit this webpage on regular basis to get updated from
most recent reports.

6. I have been surfing online more than three hours today, yet I never found any interesting article like
yours. It’s pretty worth enough for me. In my view, if all site owners
and bloggers made good content as you did, the internet will be much more useful than ever before.

7. Howdy! This is my first visit to your blog! We are a team of volunteers and starting a new project in a community in the same niche.

Your blog provided us valuable information to work on. You have done a extraordinary job!

8. Valuable information. Lucky me I found your site by accident, and I am shocked why this accident did not happened earlier! I bookmarked it.

9. Thanks for finally writing about >【CodeChef PRIMEDST】Prime Distance
On Tree – Qizy’s Database <Liked it!

changes that make the most important changes. Thanks for sharing!

11. Thank you for sharing your info. I really appreciate your efforts and I will be waiting for your next post thanks once again.

12. Excellent blog you have here.. It’s hard to find high-quality writing like
yours these days. I truly appreciate people like you! Take care!!

13. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
I’ve been looking for a plug-in like this for quite some time and was hoping maybe you
would have some experience with something like this.

14. Thank you for the good writeup. It in fact was a amusement account it.

However, how could we communicate?

15. I was wondering if you ever considered changing the layout of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way
of content so people could connect with it better. Youve got an awful lot of text for only having one or
two pictures. Maybe you could space it out better?

16. Link exchange is nothing else however it is only placing the
other person will also do same in favor of you.

17. What’s Going down i’m new to this, I stumbled upon this I have found It absolutely
helpful and it has aided me out loads. I am hoping to give a contribution & aid different users like its aided me.
Great job.

18. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get three e-mails with the same comment.
Is there any way you can remove people from that service?
Thanks a lot!

19. Heya i’m for the primary time here. I came across this board and
I to find It really useful & it helped me out much.

I am hoping to provide one thing again and aid others such as you helped me.

20. If you are going for finest contents like myself, just pay a
quick visit this web site all the time as it provides quality contents, thanks

21. I enjoy the efforts you have put in this, appreciate it for all the great articles.

22. Really informative blog article.Thanks Again. Want more.