首页 > 代码库 > BZOJ3451: Tyvj1953 Normal
BZOJ3451: Tyvj1953 Normal
题解：
好神的一道题。蒟蒻只能膜拜题解。
考虑a对b的贡献，如果a是a-b路径上第一个删除的点，那么给b贡献1。
所以转化之后就是求sigma(1/dist(i,j)),orz！！！
如果不是分母的话O（n）就可以搞，但是现在在分母上。。。
考虑转化一下，求ret[i]表示距离为i的点对有多少对。我们发现只要求出ret数组，然后就可以回答了。
如何求ret，我们用点分治。类似于RACE那道题。
对于一颗子树，我们整个信息一块统计，让它和前面的所有做卷积，更新ret，然后再把这棵子树归入前面的信息内。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 50000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 43 44 #define mod 1000000007 45 46 using namespace std; 47 48 inline int read() 49 50 { 51 52 int x=0,f=1;char ch=getchar(); 53 54 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 55 56 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 57 58 return x*f; 59 60 } 61 int n,mx,m,len,cnt,sum,tot,rt,rev[maxn],head[maxn],d[maxn],f[maxn],s[maxn],g[maxn]; 62 bool del[maxn]; 63 ll ret[maxn]; 64 const double PI=acos(-1.0); 65 struct cp 66 { 67 double x,y; 68 cp operator +(cp b){return (cp){x+b.x,y+b.y};} 69 cp operator -(cp b){return (cp){x-b.x,y-b.y};} 70 cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};} 71 }; 72 cp a[2*maxn],b[2*maxn],c[2*maxn],y[2*maxn]; 73 struct edge{int go,next;}e[2*maxn]; 74 inline void insert(int x,int y) 75 { 76 e[++tot]=(edge){y,head[x]};head[x]=tot; 77 e[++tot]=(edge){x,head[y]};head[y]=tot; 78 } 79 inline void getrt(int x,int fa) 80 { 81 s[x]=1;f[x]=0; 82 for4(i,x)if(!del[y=e[i].go]&&y!=fa) 83 { 84 getrt(y,x); 85 s[x]+=s[y]; 86 f[x]=max(f[x],s[y]); 87 } 88 f[x]=max(f[x],sum-f[x]); 89 if(f[x]<f[rt])rt=x; 90 } 91 inline void getdep(int x,int fa,int w) 92 { 93 if(w>mx)mx=w; 94 d[++cnt]=w; 95 for4(i,x)if(!del[y=e[i].go]&&y!=fa)getdep(y,x,w+1); 96 } 97 inline void get(int n) 98 { 99 n++;n=2*n-1;100 m=1,len=0;101 while(m<=n)m<<=1,len++;102 for0(i,m-1)103 {104 int x=i,y=0;105 for1(j,len)y<<=1,y|=x&1,x>>=1;106 rev[i]=y;107 }108 }109 inline void fft(cp *x,int n,int flag)110 {111 for0(i,n-1)y[rev[i]]=x[i];112 for0(i,n-1)x[i]=y[i];113 for(int m=2;m<=n;m<<=1)114 {115 cp wn=(cp){cos(2.0*PI*flag/m),sin(2.0*PI*flag/m)};116 for(int i=0;i<n;i+=m)117 {118 cp w=(cp){1,0};int mid=m>>1;119 for0(j,mid-1)120 {121 cp u=x[i+j],v=x[i+j+mid]*w;122 x[i+j]=u+v;x[i+j+mid]=u-v;123 w=w*wn;124 }125 }126 }127 if(flag==-1)for0(i,n-1)x[i].x/=n;128 }129 inline void work(int x)130 {131 //cout<<"XXXXX"<<‘ ‘<<x<<‘ ‘<<"XXXX"<<endl;132 del[x]=1;mx=0;133 for4(i,x)if(!del[y=e[i].go])134 {135 cnt=0;136 getdep(y,x,1);get(mx);137 for0(j,m-1)a[j]=(cp){g[j],0},b[j]=(cp){0,0};138 for1(j,cnt)b[d[j]].x+=1,g[d[j]]++;139 //for0(j,m-1)cout<<j<<‘ ‘<<a[j].x<<‘ ‘<<b[j].x<<endl;140 fft(a,m,1);fft(b,m,1);141 for0(j,m-1)c[j]=a[j]*b[j];142 fft(c,m,-1);143 for0(j,m-1)ret[j]+=c[j].x+0.5;144 //for0(j,m-1)cout<<j<<‘ ‘<<c[j].x<<‘ ‘<<c[j].y<<endl;145 }146 for1(i,mx)ret[i]+=g[i],g[i]=0;147 for4(i,x)if(!del[y=e[i].go])148 {149 sum=s[y];rt=0;150 getrt(y,0);151 work(rt);152 }153 } 154 155 int main()156 157 {158 159 freopen("input.txt","r",stdin);160 161 freopen("output.txt","w",stdout);162 163 n=read();164 for1(i,n-1)insert(read()+1,read()+1);165 sum=n;f[rt=0]=inf;166 getrt(1,0);167 work(rt);168 double ans=0.0;169 for1(i,n)170 ans+=(double)ret[i]/(double)(i+1);//cout<<i<<‘ ‘<<ret[i]<<endl;171 printf("%.4f\n",n+2*ans);172 173 return 0;174 175 }
3451: Tyvj1953 Normal
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 125 Solved: 60
[Submit][Status]
Description
某天WJMZBMR学习了一个神奇的算法：树的点分治！
这个算法的核心是这样的：
消耗时间=0
Solve(树 a)
消耗时间 += a 的 大小
如果 a 中 只有 1 个点
退出
否则在a中选一个点x，在a中删除点x
那么a变成了几个小一点的树，对每个小树递归调用Solve
我们注意到的这个算法的时间复杂度跟选择的点x是密切相关的。
如果x是树的重心，那么时间复杂度就是O(nlogn)
但是由于WJMZBMR比较傻逼，他决定随机在a中选择一个点作为x！
Sevenkplus告诉他这样做的最坏复杂度是O(n^2)
但是WJMZBMR就是不信>_<。。。
于是Sevenkplus花了几分钟写了一个程序证明了这一点。。。你也试试看吧^_^
现在给你一颗树，你能告诉WJMZBMR他的傻逼算法需要的期望消耗时间吗？（消耗时间按在Solve里面的那个为标准）
Input
第一行一个整数n，表示树的大小
接下来n-1行每行两个数a,b，表示a和b之间有一条边
注意点是从0开始标号的
Output
一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended
Sample Input
3
0 1
1 2
0 1
1 2
Sample Output
5.6667
HINT
n<=30000
Source
我们都爱GYZ杯
BZOJ3451: Tyvj1953 Normal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。