首页 > 代码库 > Tourists
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:
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.
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:
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 ?rst 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.
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.
样例输入
103 43 71 44 61 108 102 81 54 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+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int 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;}int n,m,k,t,p[maxn<<1],all,dep[maxn],tot,h[maxn],vis[maxn<<1],vis1[maxn],fa[maxn],st[20][maxn<<1];void init(){ for(int i=2;i<=all;i++)p[i]=1+p[i>>1]; for(int i=1;i<=19;i++) for(int j=1;(j+(1<<i)-1)<=(ll)all;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);}int query(int l,int r){ int x=p[r-l+1]; return min(st[x][l],st[x][r-(1<<x)+1]);}struct node{ int to,nxt;}e[maxn<<1];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(1); while(!S.empty()) { int now = S.top(); if(vis1[now] == 1)// if node is gray, then color black { vis1[now] = 2; st[0][++all]=dep[fa[now]]; // do things after dfs children. S.pop(); } else if(vis1[now] == 0)// if node is white, then color gray { vis1[now] = 1; st[0][++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]+1; fa[to]=now; S.push(to); } } } }}ll ans;int main(){ int i,j; //freopen("in.txt","r",stdin); while(~scanf("%d",&n)) { ans=0; all=0; tot=0; memset(dep,0,sizeof(dep)); memset(vis,0,sizeof(vis)); memset(h,0,sizeof(h)); memset(p,0,sizeof(p)); memset(vis1,0,sizeof(vis1)); rep(i,1,n-1) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } dfs(); init(); for(i=1;i<=n;i++) { for(j=i*2;j<=n;j+=i) { ans+=dep[i]+dep[j]-2*query(min(vis[i],vis[j]),max(vis[i],vis[j]))+1; } } printf("%lld\n",ans); } //system("Pause"); return 0;}
Tourists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。