walk 题解【约数】【树的直径】【枚举】

点击量：165

    考察了一些让时间复杂度变低的一些技巧？这个题本身也是很不错的。

目录

题目描述

给定一棵\(n\)个节点的树，每条边的长度为\(1\)，同时有一个权值\(w\)。定义一条路径的权值为路径上所有边的权值的最大公约数。现在对于任意\(i\in [1,n]\)，求树上所有长度为\(i\)的简单路径中权值最大的是多少。如果不存在长度为\(i\)的路径，则第\(i\)行输出\(0\)。

 

输入输出格式

输入格式：

第一行，一个整数\(n\)，表示树的大小。接下来\(n-1\)行，每行三个整数\(u,v,w\)，表示\(u,v\)之间存在一条权值为\(w\)的边。

 

输出格式：

对于每种长度，输出一行，表示答案。

 

输入输出样例

输入样例#1：

3
1 2 3
1 3 9

输出样例#1：

9
3
0

说明

对于\(30\%\)的数据，\(n\le 1000\)；

对于另外\(30\%\)的数据，\(w\le 100\)；

对于\(100\%\)的数据，\(n\le 4\times 10^5,1\le u,v\le n,w\le 10^6\)。

题解：

    这个题是比较良心的，另外\(30\%\)的数据实际上是正解的提示。

    对于前面30分，应该是比较好拿的。直接枚举起点暴力\(dfs\)，顺便求\(\gcd\)+还原现场就可以了，时间复杂度\(O(n^2\log n)\)。接下来30分，可以枚举答案\(ans\)，把图中权值为\(ans\)倍数的边取出来，算森林的直径就可以了。

    实际做法就是上面这种，只不过枚举的方式需要优化。我们预处理出每条边的所有因数，可以得到以每个因数为答案的边集。预处理复杂度为\(O(n\sqrt w)\)

    然后枚举答案，每次重新建图。理论上约数个数可以达到上界\(\frac w2\)，因此如果全部枚举，复杂度很快就达到了\(O(nw)\)。因此需要在上面预处理出的链表/vector中选边加边，这样的话每条边出现的次数最多是\(O(\sqrt{w_i})\)，但是数\(x\)的期望约数个数是\(O(\log x)\)，因此这个根号上界是非常松的。那么我们每次建图找直径，复杂度就是\(O(\sum_{i=1}^{10^6}边权能被i整除的边数)\)。

    我们发现复杂度是跑到\(2s\)以内了，但是每次（\(10^6\)次）的初始化数量级都是\(4\times 10^5\)的，我们就要学着节约资源——用多少恢复多少。在加边的过程中，只把变过的点的head复原，剩下的因为本来就是初始值，没有必要复原；接着让ecnt=-1即可。

    重构代码大法好！(ﾉﾟ∀ﾟ)ﾉ 

Code：

#include<cstdio>
#include<cstring>
#include<vector>
int Max(int x,int y)
{
    return x>y?x:y;
}
using std::vector;
vector<int> r[1000010];//r[i]存i能整除边权的边的编号
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[800100];
int head[400100],ecnt=-1;
int cgd[400100],cnt=0;//记录哪些被修改过了
void add(int from,int to)
{
    if(head[from]==-1)
        cgd[++cnt]=from;
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    if(head[to]==-1)
        cgd[++cnt]=to;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int from[400100],to[400100],v[400100];
int used[400100],idx=0,mx=0,d,now=0;
void dfs(int x,int from)
{
    used[x]=idx;
    if(now>mx)
    {
        mx=now;
        d=x;
    }
    ++now;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
            dfs(e[i].n,x);
    --now;
}
int work(int x)
{
    mx=0;
    dfs(x,x);
    dfs(d,d);
    return mx;
}
int ans[400100];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d",&from[i],&to[i],&v[i]);
        for(int j=1;j*j<=v[i];++j)
            if(v[i]%j==0)
            {
                r[j].push_back(i);
                if(j*j!=v[i])
                    r[v[i]/j].push_back(i);
            }
    }
    memset(head,-1,sizeof(head));
    for(int i=1;i<=1000000;++i)
    {
        cnt=0;
        for(vector<int>::iterator it=r[i].begin();it!=r[i].end();++it)
            add(from[*it],to[*it]);
        ++idx;
        int mxx=0;
        for(vector<int>::iterator it=r[i].begin();it!=r[i].end();++it)
            if(used[to[*it]]!=idx)
                mxx=Max(mxx,work(to[*it]));
        ans[mxx]=i;
        ecnt=-1;
        for(int j=1;j<=cnt;++j)
            head[cgd[j]]=-1;
    }
    for(int i=n;i;--i)
        ans[i]=Max(ans[i+1],ans[i]);
    for(int i=1;i<=n;++i)
        printf("%d\n",ans[i]);
    return 0;
}