Tourists

时间：2023-03-09 07:15:45
Tourists

Tourists

时间限制: 5 Sec  内存限制: 64 MB

题目描述

In Tree City, there are n tourist attractions uniquely labeled 1 to n. The attractions are connected by a set of n − 1 bidirectional roads in such a way that a tourist can get from any attraction to any other using some path of roads.
You are a member of the Tree City planning committee. After much research into tourism, your committee has discovered a very interesting fact about tourists: they LOVE number theory! A tourist who visits an attraction with label x will then visit another attraction with label y if y > x and y is a multiple of x. Moreover, if the two attractions are not directly connected by a road thetourist will necessarily visit all of the attractions on the path connecting x and y, even if they aren’t multiples of x. The number of attractions visited includes x and y themselves. Call this the length of a path.
Consider this city map:
Tourists

Here are all the paths that tourists might take, with the lengths for each:
1 → 2 = 4, 1 → 3 = 3, 1 → 4 = 2, 1 → 5 = 2, 1 → 6 = 3, 1 → 7 = 4,
1 → 8 = 3, 1 → 9 = 3, 1 → 10 = 2, 2 → 4 = 5, 2 → 6 = 6, 2 → 8 = 2,
2 → 10 = 3, 3 → 6 = 3, 3 → 9 = 3, 4 → 8 = 4, 5 → 10 = 3
To take advantage of this phenomenon of tourist behavior, the committee would like to determine the number of attractions on paths from an attraction x to an attraction y such that y > x and y is a multiple of x. You are to compute the sum of the lengths of all such paths. For the example above, this is: 4 + 3 + 2 + 2 + 3 + 4 + 3 + 3 + 2 + 5 + 6 + 2 + 3 + 3 + 3 + 4 + 3 = 55.

输入

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of an integer n (2 ≤ n ≤ 200,000) indicating the number of attractions. Each of the following n−1 lines will consist of a pair of space-separated
integers i and j (1 ≤ i < j ≤ n), denoting that attraction i and attraction j are directly connected by a road. It is guaranteed that the set of attractions is connected.

输出

Output a single integer, which is the sum of the lengths of all paths between two attractions x and y such that y > x and y is a multiple of x.

样例输入

10

3 4

3 7

1 4

4 6

1 10

8 10

2 8

1 5

4 9

样例输出

55
分析：LCA裸题；
　　　注意dfs层数太深会爆，所以需要手写栈；
代码：
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <unordered_map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define Lson L, mid, ls[rt]

#define Rson mid+1, R, rs[rt]

#define sys system("pause")

const int maxn=2e5+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

inline ll read()

{

    ll x=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,k,t,p[maxn<<],all,dep[maxn],tot,h[maxn],vis[maxn<<],vis1[maxn],fa[maxn],st[][maxn<<];

void init()

{

    for(int i=;i<=all;i++)p[i]=+p[i>>];

    for(int i=;i<=;i++)

        for(int j=;(j+(<<i)-)<=(ll)all;j++)

            st[i][j]=min(st[i-][j],st[i-][j+(<<(i-))]);

}

int query(int l,int r)

{

    int x=p[r-l+];

    return min(st[x][l],st[x][r-(<<x)+]);

}

struct node

{

    int to,nxt;

}e[maxn<<];

void add(int x,int y)

{

    tot++;

    e[tot].to=y;

    e[tot].nxt=h[x];

    h[x]=tot;

}

stack<int>S;

void dfs()

{

    S.push();

    while(!S.empty())

    {

        int now = S.top();

        if(vis1[now] == )// if node is gray, then color black

        {

            vis1[now] = ;

            st[][++all]=dep[fa[now]];

            // do things after dfs children.

            S.pop();

        }

        else if(vis1[now] == )// if node is white, then color gray

        {

            vis1[now] = ;

            st[][++all]=dep[now];

            vis[now]=all;

            // do things before dfs children.

            for(int i=h[now];i;i=e[i].nxt)

            {

                int to=e[i].to;

                if(!vis1[to])

                {

                    dep[to]=dep[now]+;

                    fa[to]=now;

                    S.push(to);

                }

            }

        }

    }

}

ll ans;

int main()

{

    int i,j;

    //freopen("in.txt","r",stdin);

    while(~scanf("%d",&n))

    {

        ans=;

        all=;

        tot=;

        memset(dep,,sizeof(dep));

        memset(vis,,sizeof(vis));

        memset(h,,sizeof(h));

        memset(p,,sizeof(p));

        memset(vis1,,sizeof(vis1));

        rep(i,,n-)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            add(a,b),add(b,a);

        }

        dfs();

        init();

        for(i=;i<=n;i++)

        {

            for(j=i*;j<=n;j+=i)

            {

                ans+=dep[i]+dep[j]-*query(min(vis[i],vis[j]),max(vis[i],vis[j]))+;

            }

        }

        printf("%lld\n",ans);

    }

    //system("Pause");

    return ;

}

相关文章