首页 > 代码库 > [51nod1709]复杂度分析
[51nod1709]复杂度分析
给出一棵n个点的树(以1号点为根),定义dep[i]为点i到根路径上点的个数。众所周知,树上最近公共祖先问题可以用倍增算法解决。现在我们需要算出这个算法精确的复杂度。我们定义计算点i和点j最近公共组先的精确复杂度为bit[dep[i]-dep[lca(i,j)]]+bit[dep[j]-dep[lca(i,j)]](bit[i]表示i在二进制表示下有多少个1,lca(i,j)表示点i和点j的最近公共祖先)。为了计算平均所需的复杂度为多少,请你帮忙计算任意两点计算最近公共组先所需复杂度的总和。
即计算 sum{ bit[dep[i]-dep[lca(i,j)]]+bit[dep[j]-dep[lca(i,j)]] } ,1<=i<n,i+1<=j<=n;
Input
第一行一个数n表示点数(1<=n<=100,000)
接下来n-1行每行两个数x,y表示一条边(1<=x,y<=n)
Output
一个数表示答案
抱sxt大腿系列。。大概思路就是统计每个点往上跳每一步对答案的贡献。。先倍增预处理出每个点的那些父亲还有到父亲的那条边。
大概就是统计一下能从子树里跳到当前点的节点数,那些点就能当前父亲其他儿子里能跳到父亲的节点一起贡献。。。
当然不能每次直接跑。。就把查询都存到到父亲的边里面,最后再dfs一遍统计。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #include<cstdlib> 8 #include<bitset> 9 //#include<ctime>10 #define ll long long11 #define ull unsigned long long12 #define ui unsigned int13 #define d double14 //#define ld long double15 using namespace std;16 const int maxn=100233,mxnode=maxn<<1;17 struct zs{int too,pre;}e[maxn<<1];int tot,last[maxn];18 int fa[maxn][18],fae[maxn][18],num[maxn],pos[maxn],TIM,sz[maxn];19 ll sum[maxn],sume[maxn<<1];20 int i,j,k,n,m;21 ll ans;22 23 int ra,fh;char rx;24 inline int read(){25 rx=getchar(),ra=0,fh=1;26 while((rx<‘0‘||rx>‘9‘)&&rx!=‘-‘)rx=getchar();27 if(rx==‘-‘)fh=-1,rx=getchar();28 while(rx>=‘0‘&&rx<=‘9‘)ra=ra*10+rx-48,rx=getchar();return ra*fh;29 }30 31 inline void dfs(int x){32 register int i,to;pos[++TIM]=x,sz[x]=num[x]=1;33 for(i=1;i<18;i++)fa[x][i]=fa[fa[x][i-1]][i-1],fae[x][i]=fae[fa[x][i-1]][i-1];34 for(i=last[x];i;i=e[i].pre)if((to=e[i].too)!=fa[x][0])35 fa[to][0]=x,fae[to][0]=i,dfs(to),sz[x]+=sz[to];36 }37 inline void DFS(int x){38 register int i,to;39 for(i=last[x];i;i=e[i].pre)if((to=e[i].too)!=fa[x][0])40 ans+=1ll*sume[i]*(sz[x]-sz[to]),DFS(to);41 }42 inline void insert(int a,int b){43 e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,44 e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;45 }46 int main(){47 n=read();register int i,j;48 for(i=1;i<n;i++)insert(read(),read());49 dfs(1);50 int f;51 for(j=0;j<18;j++)for(i=1;i<=n;i++)if((f=fa[k=pos[i]][j]))52 num[f]+=num[k],sum[f]+=num[k]+sum[k],sume[fae[k][j]]+=num[k]+sum[k];53 DFS(1),printf("%lld\n",ans);54 }
[51nod1709]复杂度分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。