Zsnuo's Blog

Love is a touch and yet not a touch.

【codeforces 983E】NN country

Description

In the NN country, there are n cities, numbered from 1 to n, and n?1 roads, connecting them. There is a roads path between any two cities.

There are m bidirectional bus routes between cities. Buses drive between two cities taking the shortest path with stops in every city they drive through. Travelling by bus, you can travel from any stop on the route to any other. You can travel between cities only by bus.

You are interested in q questions: is it possible to get from one city to another and what is the minimum number of buses you need to use for it?

Input

The first line contains a single integer n (2≤n≤2?10⁵) — the number of cities.

The second line contains n?1 integers p₂,p₃,…,p_n (1≤p_i<i), where p_i means that cities p_i and i are connected by road.

The third line contains a single integer m (1≤m≤2?10⁵) — the number of bus routes.

Each of the next m m lines contains 2 integers a and b (1≤a,b≤n, a≠b), meaning that there is a bus route between cities a and b. It is possible that there is more than one route between two cities.

The next line contains a single integer q (1≤q≤2?10⁵) — the number of questions you are interested in.

Output

Print the answer for each question on a separate line. If there is no way to get from one city to another, print ?1. Otherwise print the minimum number of buses you have to use.

題意：給定一棵 $n$ 個點的樹， $m$ 條鏈， $q$ 個詢問，每次詢問 $a$ 到 $b$ 之間的路徑最少可用幾條給定鏈完全覆蓋，無解輸出 $-1$ 。

分析：

對于每一條 $a$ 與$b$ 間的路徑，都可拆分為 $a$ 到 $lca$ 的路徑和 $b$ 到 $lca$ 的路徑

采用貪心策略， $low[x][i]$ 表示從 $x$ 點出發向上選擇不超過 $2^i$ 條鏈可抵達的深度最淺的點。這時對于每一個詢問可將詢問的兩個端點修改為利用貪心策略跳到的深度大于 $lca$ 且深度最小的節點，并記錄下答案，這個過程可以用倍增完成。注意特判端點即 $lca$ 的情況。

然后出現兩種情況。若修改后的兩個端點出現在同一條給定鏈上，答案為原答案 $+1$ ，否則答案為原答案 $+2$ 。問題模型轉換為，每次詢問一個點對是否出現在同一條給定鏈上。記錄下 $dfs$ 序，在深搜過程中利用樹狀數組統計即可。

時間復雜度 $O(nlogn)$ 。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 #define LL long long
  6 using namespace std;
  7 const int N=2e5+5;
  8 const int inf=0x3f3f3f3f;
  9 int n,m,Q,cnt,val,x,y,ind;
 10 int deep[N],in[N],out[N],last[N];
 11 int first[N],ans[N],tr[N];
 12 int fa[N][20],low[N][20];
 13 bool ok[N];
 14 vector<int> a[N],b[N];
 15 struct edge{int to,next;}e[N];
 16 struct chain{int x,y,t;}c[N],q[N];
 17 int read()
 18 {
 19     int x=0,f=1;char c=getchar();
 20     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 21     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 22     return x*f;
 23 }
 24 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
 25 void dfs(int x)
 26 {
 27     in[x]=++ind;
 28     for(int i=1;(1<<i)<=deep[x];i++)
 29         fa[x][i]=fa[fa[x][i-1]][i-1];
 30     for(int i=first[x];i;i=e[i].next)
 31     {
 32         deep[e[i].to]=deep[x]+1;
 33         dfs(e[i].to);
 34     }
 35     out[x]=ind;
 36 }
 37 int lca(int x,int y)
 38 {
 39     if(deep[x]<deep[y])swap(x,y);
 40     int d=deep[x]-deep[y];
 41     for(int i=0;(1<<i)<=d;i++)
 42         if((1<<i)&d)x=fa[x][i];
 43     if(x==y)return x;
 44     for(int i=17;i>=0;i--)
 45         if((1<<i)<=deep[x]&&fa[x][i]!=fa[y][i])
 46             x=fa[x][i],y=fa[y][i];
 47     return fa[x][0];
 48 }
 49 void dfslow(int x)
 50 {
 51     for(int i=first[x];i;i=e[i].next)
 52     {
 53         int to=e[i].to;dfslow(to);
 54         if(deep[low[to][0]]<deep[low[x][0]])
 55             low[x][0]=low[to][0];
 56     }
 57 }
 58 int find(int x,int t)
 59 {
 60     if(deep[low[x][17]]>deep[t]){val=-inf;return -1;}
 61     if(x==t){val=-1;return 0;}
 62     val=0;
 63     for(int i=17;i>=0;i--)
 64         if(deep[low[x][i]]>deep[t])
 65             x=low[x][i],val|=(1<<i);
 66     return x;
 67 }
 68 int lowbit(int x){return x&(-x);}
 69 void add(int x,int v){for(;x<=n;x+=lowbit(x))tr[x]+=v;}
 70 int query(int x){int ans=0;for(;x;x-=lowbit(x))ans+=tr[x];return ans;}
 71 void work(int x)
 72 {
 73     for(int sz=b[x].size(),i=0;i<sz;i++)
 74     {
 75         int t=b[x][i];
 76         last[t]=query(out[q[t].y])-query(in[q[t].y]-1);
 77     }
 78     for(int sz=a[x].size(),i=0;i<sz;i++)add(in[a[x][i]],1);
 79     for(int i=first[x];i;i=e[i].next)work(e[i].to);
 80     for(int sz=b[x].size(),i=0;i<sz;i++)
 81     {
 82         int t=b[x][i];
 83         if(query(out[q[t].y])-query(in[q[t].y]-1)!=last[t])ok[t]=true;
 84     }
 85 }
 86 int main()
 87 {
 88     n=read();
 89     for(int i=2;i<=n;i++)
 90         fa[i][0]=read(),ins(fa[i][0],i);
 91     dfs(1);
 92     for(int i=1;i<=n;i++)low[i][0]=i;
 93     m=read();
 94     for(int i=1;i<=m;i++)
 95     {
 96         c[i].x=read();c[i].y=read();
 97         c[i].t=lca(c[i].x,c[i].y);
 98         if(deep[c[i].t]<deep[low[c[i].x][0]])
 99             low[c[i].x][0]=c[i].t;
100         if(deep[c[i].t]<deep[low[c[i].y][0]])
101             low[c[i].y][0]=c[i].t;
102         a[c[i].x].push_back(c[i].y);
103         a[c[i].y].push_back(c[i].x);
104     }
105     dfslow(1);
106     for(int t=1;t<=n;t++)
107         for(int i=1;i<=17;i++)
108             low[t][i]=low[low[t][i-1]][i-1];
109     Q=read();
110     for(int i=1;i<=Q;i++)
111     {
112         q[i].x=read();q[i].y=read();
113         q[i].t=lca(q[i].x,q[i].y);
114         ans[i]=2;
115         x=find(q[i].x,q[i].t);ans[i]+=val;
116         y=find(q[i].y,q[i].t);ans[i]+=val;
117         if(x>0&&y>0)
118         {
119             q[i].x=x;q[i].y=y;
120             b[x].push_back(i);
121         }
122     }
123     work(1);
124     for(int i=1;i<=Q;i++)
125         if(ok[i])ans[i]--;
126     for(int i=1;i<=Q;i++)
127         printf("%d\n",ans[i]<0?-1:ans[i]);
128     return 0;
129 }

View Code

posted @ 2018-05-18 22:07 Zsnuo 閱讀(931) 評論(0) 收藏舉報

刷新頁面返回頂部