「Codeforces 983E」NN country

发表于

给定一棵 nn 个点的树， mm 条链， qq 个询问，每次询问 aa 到 bb 之间的路径最少可用几条给定链完全覆盖，无解输出 −1-1 。

Constraints

2≤n≤2⋅1052\leq n \leq 2\cdot 10 ^5 ，1≤m≤2⋅1051\leq m \leq 2\cdot 10 ^5 ，1≤q≤2⋅1051\leq q \leq 2\cdot 10 ^5

Solution

对于每一条 aa 与 bb 间的路径，都可拆分为 aa 到 lcalca 的路径和 bb 到 lcalca 的路径

采用贪心策略， low[x][i]low[x][i] 表示从 xx 点出发向上选择不超过 2i2^i 条链可抵达的深度最浅的点。这时对于每一个询问可将询问的两个端点修改为利用贪心策略跳到的深度大于 lcalca 且深度最小的节点，并记录下答案，这个过程可以用倍增完成。注意特判端点即 lcalca 的情况。

然后出现两种情况。若修改后的两个端点出现在同一条给定链上，答案为原答案 +1+1 ，否则答案为原答案 +2+2 。问题模型转换为，每次询问一个点对是否出现在同一条给定链上。记录下 dfs 序，在深搜过程中利用树状数组统计即可。

时间复杂度 O(nlogn)O(nlogn) 。

Code

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