还不会做！ 树上的gcd 树分治 UOJ33

题目链接：http://uoj.ac/problem/33

题解链接：http://vfleaking.blog.uoj.ac/blog/38

现在感觉到了做OI的层层递进的思路的伟大之处，作为一个大学才开始接触C的人只能orz了

算法一：

傻逼暴力+lca，所以树O（n*n*logn）

所以10分

算法二：（orz我竟然看了半天）

对于随机生成的树，那么树的高度都是log层的，所以省略去算法一中的傻逼暴力。因为每一层的树高都是log，所以我们只需要暴力树根u，然后以u为根，dfs（u）的所有子节点，并且用cnt[h]记录高度为h的子树的个数即可。最后我们就是暴力h1和h2，然后用cnt[h1]*cnt[h2]，然后加入到ans[gcd(h1, h2)]里面即可。因为h1和h2的高度是log，所以我们最终复杂度为O(N * logn * logn)。并且dfs也都是dfs子树，子树的平均分摊也肯定是logn次

所以30分

算法三：（早上看的时候完全没有反应过来，上完一下午的课回来再看发现，还是很难= =）

通过算法二的提示我们发现，我们只需要知道ans[gcd(h1, h2)]而已，所以，我们假定d=gcd(h1, h2)，那么对于每一条链，设他的高度为hi，那么他为d倍数的个数为hi/d个，

策爷的代码，怪我水平不够，代码看不懂

#include
#include
#include
#include
#include
//#include
#define MAX 200005
using namespace std;
int n;
struct edge{int v,next;}e[MAX];int etot=0;int g[MAX];
void addedge(int u,int v){///建立有根树e[etot].v=v;e[etot].next=g[u];g[u]=etot++;
}
typedef long long ll;
ll ans[MAX]={0};///ans(i)表示两棵子树间深度为i的倍数的值的个数
ll ans2[MAX]={0};
int h[MAX],pre[MAX];///h表示目前树的高度，pre(x)表示节点x的fa
int off[MAX]={0};///off(i)表示目前是否对i节点打标记，就表示是否成为过重心/**orz 这重心找的太强了，比dfs不知道快多少*/
int qu[MAX],sz[MAX],bobo[MAX];//这个bobo应该是bool的意思，表示是否能选择
int findc(int rt){int p=0,q=0;qu[q++]=rt;///就是queuewhile(p!=q){///bfs对所有子节点进行初始化(当然，也可以在这里进行pre节点的修改)int u=qu[p++];bobo[u]=sz[u]=1;for (int i=g[u];~i;i=e[i].next)if(!off[e[i].v])///如果没有访问过，就刚入bfs的节点qu[q++]=e[i].v;}for (int i=q-1;i>=0;i--){///迭代使用if(bobo[qu[i]] && sz[qu[i]]*2>=q)return qu[i];///重心肯定是树size的一半，所以sz肯定也是重心的一半左右sz[pre[qu[i]]]+=sz[qu[i]];///对他的父亲节点的sz进行更新if(sz[qu[i]]*2>q)bobo[pre[qu[i]]]=0;///如果目前节点的sz*2比q大了，那么父亲节点也肯定比他大了，所以对他的父亲节点都是false
    }
}int nub[MAX];///统计这一棵子树，深度为h的有几个
/**统计深度为h的有几个，并且返回最大深度*/
int bfs(int rt,int *nub,int hh){///注意，这里的hh可能会发生改变的int p=0,q=0;qu[q++]=rt;while(p!=q){///bfs出所有的节点int u=qu[p++];for (int i=g[u];~i;i=e[i].next)if(!off[e[i].v])qu[q++]=e[i].v;}///h在main函数的输入中就已经得到了int hmax=h[qu[q-1]]-h[rt]+hh;///得到最大深度，因为bfs到的最大深度就是for (int i=0;i<=hmax;i++)nub[i]=0;///对目前深度一下的进行初始化for (int i=0;i){nub[h[qu[i]]-h[rt]+hh]++;///统计目前深度的cnt的个数
    }/*if (hh == 0){for (int i = 0; i < 10; i++){printf("%d ", nub[i]);}cout << endl;}if (hh == 0) printf("hmax = %d\n", hmax);*/return hmax;
}int tmp[MAX];///tmp[j]就是保存所有子树中被j整除的个数
ll tmpsq[MAX];///tmpsq[j]是保存了所有子树中自身两两搭配的个数
int nsu[MAX];///nsu表示所有子树的高度为j的数目
int tmpnu[MAX],*start[MAX],tmph[MAX];
int ord[MAX];
int cmp(int i,int j){return tmph[i]<tmph[j];}
int ind=0;
int check[MAX]={0},val[MAX];void work(int rt){int c=findc(rt);///找到重心off[c]=1;///对重心进行标记/*u和v是在同一棵子树里面*/int hmax=0;///暴力所有的重心的子节点//printf("cetroid = %d\n", c);//这里从来不计算高度=0的时候的东西for (int i=g[c];~i;i=e[i].next)if(!off[e[i].v]){int h=bfs(e[i].v,nub,1);///这里之所以是1，因为他是重心的子节点if(h>hmax){///表示高度为j的是1，并且在这里初始化for (int j=hmax+1;j<=h;j++)nsu[j]=0,tmp[j]=tmpsq[j]=1;hmax=h;}for (int j=1;j<=h;j++){nsu[j]+=nub[j];///nsu表示所有子树的高度为j的数目int sum=0;///k是j的倍数，sum保存能被j整除的数的个数for (int k=j;k<=h;k+=j) sum+=nub[k];///tmp[j]就是保存所有子树中被j整除的个数///tmpsq[j]是保存了所有子树中自身两两搭配的个数tmp[j]+=sum; tmpsq[j]+=1ll*sum*sum;}}/*但是存在一个疑问点就是，如果两个都是2*d怎么解决呢？*////tmp[i]*tmp[i]表示所有子树的两两搭配，但是不包括自身的两两搭配for (int i=1;i<=hmax;i++)ans[i]+=(1ll*tmp[i]*tmp[i]-tmpsq[i])>>1;int u,num=0;///num表示往上爬几次int *st=tmpnu;///st为tmpnu数组///往重心上面的结点爬for (u=pre[c]; u && !off[u]; u=pre[u]){off[u]=1;///对父亲结点打标记start[++num]=st;///让start[++num]等于st数组，并且复制给他ord[num]=num;///记录编号tmph[num]=bfs(u,st,0);///这里之所以为0因为st是根///因为u是之前的fa，所以这里要+1，表示的就是往右边移动一步//表明st的移动并不对start存在影响
/*printf("num = %d\n", num);cout << "st1" << endl;for (int j = 0; j < 10; j++){printf("%d ", st[j]);}cout << endl;printf("start1\n");for (int i = 0; i < 10; i++)printf("%d ", start[num][i]);cout << endl;
*/st+=tmph[num]+1;///然后让st指针移动maxn deep+1步,把所有的东西给清除掉?//for (int j = 0; j <= tmph[num] + 1; j++) st[j] = 0;
/*printf("tmph[%d] = %d\n", num, tmph[num]);cout << "st2" << endl;for (int j = 0; j < 10; j++){printf("%d ", st[j]);}cout << endl;cout << "start2" << endl;for (int i = 0; i < 10; i++)printf("%d ", start[num][i]);cout << endl;
*/}///对所有的东西标记去除，因为这里表示的就是不断地往上面走for (int v=pre[c]; v!=u; v=pre[v]) off[v]=0;/*后面这里完全看不懂啊TAT*/for (int i=0;i<=hmax;i++){ans2[i+1]+=nsu[i];ans2[i+num+1]-=nsu[i];}///根据树的高度进行排序sort(ord+1,ord+1+num,cmp);int tms=0;for (int h=1,cur=1;cur<=num;h++){ind++;///找到高度>=h的，因为ord是排序好了的while(cur<=num && tmph[ord[cur]];for (int i=cur;i<=num;i++){int s=0,t;///加上高度是j的倍数的东西for (int j=h;j<=tmph[ord[i]];j+=h)s+=start[ord[i]][j];if(check[ord[i]%h]==ind)t=val[ord[i]%h],tms++;else{int ss=h-(ord[i]-1)%h-1;t=0;for (int j=ss;j<=hmax;j+=h)t+=nsu[j],tms++;check[ord[i]%h]=ind;val[ord[i]%h]=t;}ans[h]+=1ll*s*t;}}///也就是说，重心必须是目前的rtif(c!=rt)work(rt);///继续dfsfor (int i=g[c];~i;i=e[i].next)if(!off[e[i].v])work(e[i].v);
}int main(){nsu[0]=1;///自己到自己的树高就是0memset(g,-1,sizeof(g));scanf("%d",&n);for (int i=2;i<=n;i++){///输入int x;scanf("%d",&x);h[i]=h[x]+1;pre[i]=x;///因为x是h[i]的fa，所以h[i]的深度比h[x]要大1.然后在此时记录i的父亲是xaddedge(x,i);///建立单向边，即有根树if(x>=i)return 0;///因为题目保证了i>x，所以这个for循环里面可以这么写
    }work(1);for (int i=n-1;i>=1;i--){for (int j=2*i;j<=n-1;j+=i) ans[i]-=ans[j];}for (int i=2;i<=n-1;i++) ans2[i]+=ans2[i-1];for (int i=1;i<=n-1;i++) printf("%lld\n",ans[i]+ans2[i]);return 0;
}
/*
7
1
2
3
3
1
2
*/

然后就是这位大牛的代码，终于看懂了，是我太菜了，晚上我再重敲一遍

#include
#include
#include
#include
#include
using namespace std;int read()
{int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f;
}
#define maxn 200010int n,m,fa[maxn],root,block,siz;
struct EdgeNode{int next,to;}edge[maxn<<1];
int head[maxn],cnt;
///插入双向边
void add(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
void insert(int u,int v) {add(u,v); add(v,u);}
/**/
int size[maxn],maxx[maxn]; bool visit[maxn];///得到重心，root就是重心
void Getroot(int now,int fa){size[now]=1; maxx[now]=0;for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=fa && !visit[edge[i].to]){Getroot(edge[i].to,now);size[now]+=size[edge[i].to];maxx[now]=max(maxx[now],size[edge[i].to]);}maxx[now]=max(maxx[now],siz-size[now]);if (maxx[now]now;
}int num[maxn],deep[maxn];///deep表示目前节点的深度，num[i]表示深度为i的节点有几个
int tmp;///表示最大深度
///得到最大深度
void DFSdeep(int now,int fa){num[deep[now]]++;for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=fa && !visit[edge[i].to]){deep[edge[i].to]=deep[now]+1;DFSdeep(edge[i].to,now);}if (deep[now]>tmp) tmp=deep[now];
}long long S[maxn],Ans[maxn],ans[maxn];
long long tim[maxn],Num[maxn],Tim[maxn],f[510][510];
/*
tim(i)表示当前子树里面的距离为i的倍数的数目
Tim(i)表示除了当前子树之外的其他子树的距离是i的倍数的数目
S(i)=tim[i]*Tim[i]表示两个子树之间相乘，就是ans(i)
num(i)就记录当前子树内距离根为i的有几个点
Num(i)就表示除了当前子树外，距离根为i的有几个点f(i,j)表示目前深度为tmp，走j的倍数步的节点的个数是多少？然后Ans[i]只记录(u, v)在同一条链上的，即LCA(u,v) = u 或者 LCA(u, v) = v
*/
void GetAns(int now)
{visit[now]=1;int maxd=0,Maxd=0;///maxd表示当前子树的最大的deep，Maxd表示其他子树目前最大的Maxdeepfor (int i=head[now]; i; i=edge[i].next)///暴力子节点，且不暴力faif (!visit[edge[i].to] && edge[i].to!=fa[now]){deep[edge[i].to]=1;///对刚开始的位置定义深度为1tmp=0;///tmp表示最深的深度DFSdeep(edge[i].to,now);///寻找最深的深度if (tmp>maxd) maxd=tmp;///修改最大深度for (int j=1; j<=tmp; j++)for (int k=j; k<=tmp; k+=j)tim[j]+=num[k];for (int j=1; j<=tmp; j++)///Ans[j]在这个时候加入，因为高度为j的一定是自己的gcdNum[j]+=num[j],Ans[j]+=num[j],S[j]+=tim[j]*Tim[j],Tim[j]+=tim[j],tim[j]=0,num[j]=0;///对tim和num初始化
            }Num[0]=1;///高度为0的在这个时候放入int zz=0,ss=now;for (int i=fa[now]; !visit[i]&&i; ss=i,i=fa[i]){tmp=0;  zz++;///zz表示往上面走几步for (int j=head[i]; j; j=edge[j].next)///得到目前的最大深度if (edge[j].to!=fa[i] && !visit[edge[j].to] && edge[j].to!=ss)deep[edge[j].to]=1,DFSdeep(edge[j].to,i);if (tmp>Maxd) Maxd=tmp;for (int j=1; j<=tmp; j++)///计算为k的倍数的东西for (int k=j; k<=tmp; k+=j)tim[j]+=num[k];///tt就是小的那个，tmp表示最大深度，block表示块的大小int tt = min(tmp, block);for (int j=1; j<=tt; j++){if (f[j][zz%j]==-1)///小于sqrt(n)的我们提前储存起来分治，这样就防止复杂度过高
                        {f[j][zz%j]=0;for (int k=(j-zz%j)%j; k<=maxd; k+=j){///请注意(j-zz%j)和(j-zz%j)%j之间的区别f[j][zz%j]+=Num[k];}}///zz%j其实是一样的S[j]+=f[j][zz%j]*tim[j];}for (int j=block+1; j<=tmp; j++)///如果>j的话tim[j]for (int k=(j-zz%j)%j; k<=maxd; k+=j)S[j]+=Num[k]*tim[j];///不放入Num和Tim之中for (int j=1; j<=tmp; j++) tim[j]=0,num[j]=0;/*这个Ans是做啥的？*/Ans[zz]++;///因为每次往上面走一步,所以要加上从重心开始到这个点的cnt
        }int l=1,r=0;///这个的作用是，莫队？，表示区间[i-zz, i-1]/*这一步也看不懂*/long long tmpans=0;
/*
5
1
2
3
4
*/
/*printf("cetroid = %d\n", now);for (int i = 0; i <= maxd + zz; i++)printf("%d ", Num[i]);cout << endl;printf("zz = %d maxd = %d\n", zz, maxd);
*/
/**
终于弄明白了这里是什么意思了，Ans(i)的定义是不变的，所以i就表示距离是i的有几个，然后之前不是有一个向上
爬的过程嘛，另LCA为这个向上爬的每一个点，那么要满足在zz个之中深度在i的只有区间[i-zz,i-1]，因为还有一个
节点并没有算上去！
*/for (int i=2; i<=zz+maxd; i++){///往上走了zz步，然后又+上原来的最大深度，所以i表示最大深度tmpans += r+10;tmpans -= l+zz0;Ans[i]+=tmpans;printf("i = %d l = %d r = %d Ans[%d] = %I64d tmpans = %I64d\n", i, l, r, i, Ans[i], tmpans);}int tt = min(Maxd, block);///清空for (int i=1; i<=tt; i++)for (int j=0; j<=i-1; j++)f[i][j]=-1;for (int i=0; i<=maxd; i++) Num[i]=0,Tim[i]=0;///这里是重新开始分治for (int i=head[now]; i; i=edge[i].next)if (!visit[edge[i].to]){root=0;siz=size[edge[i].to];Getroot(edge[i].to,now);GetAns(root);}
}int main(){n=read(); block=(int)sqrt(n);for (int i=2; i<=n; i++)fa[i]=read(),insert(fa[i],i);maxx[root]=0x7fffffff;siz=n;memset(f,-1,sizeof(f));Getroot(1,0);///得到重心GetAns(root);///dfs从重心开始for (int i=n-1; i; i--){ans[i]=S[i];for (int j=i+i; j<=n-1; j+=i)///为因为S(i)表示能被i整除的，但是可能存在两个都是大于i的东西的，所以我们这里要容斥一下ans[i]-=ans[j];}for (int i=1; i<=n-1; i++) printf("%lld\n",ans[i]+Ans[i]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！