QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#562537#9295. Treeshopzjy0001WA 4ms79864kbC++178.2kb2024-09-13 18:20:312024-09-13 18:20:32

Judging History

This is the latest submission verdict.

  • [2024-09-13 18:20:32]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 79864kb
  • [2024-09-13 18:20:31]
  • Submitted

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5,INF=1e9;
struct Tree{
    int n,tim,D,cnt;
    vector<int>G[N];
    pair<int,int>dp[N];
    int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[N];
    inline void init(int _n){
        n=_n;
    }
    inline void add(int u,int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    inline void dfs1(int u,int fa){
        sz[u]=1,son[u]=0,f[u]=fa,d[u]=fa?d[fa]+1:0;
        for(auto v:G[u])if(v!=fa)dfs1(v,u),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
    }
    inline void dfs2(int u,int fa,int tp){
        top[u]=tp,rk[dL[u]=++tim]=u;
        if(son[u])dfs2(son[u],u,tp);
        for(auto v:G[u])if(v!=fa&&v!=son[u])dfs2(v,u,v);
        dR[u]=tim;
    }
    inline int LCA(int x,int y){
        for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
        return dL[x]<dL[y]?x:y;
    }
    inline int dist(int x,int y){
        return d[x]+d[y]-d[LCA(x,y)]*2;
    }
    struct{
        int a[N],dq[N],df[N];
        int ST[20][N];
        pair<int,int>dp[N][3],tmp[6];
        int n,*sz,*d,*top,*dL,*dR,*rk,*f;
        vector<int>*G;
        inline int LCA(int x,int y){
            for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
            return dL[x]<dL[y]?x:y;
        }
        inline int dist(int x,int y){
            return d[x]+d[y]-d[LCA(x,y)]*2;
        }
        inline void Dp1(int u,int fa){
            df[u]=-INF,dq[u]=-INF;
            dp[u][0]=dp[u][1]=dp[u][2]=make_pair(-INF,0);
            if(a[u])dp[u][0]=make_pair(0,u);
            for(auto v:G[u])if(v!=fa){
                Dp1(v,u);
                if(dp[v][0].first+1>dp[u][0].first)
                    dp[u][2]=dp[u][1],dp[u][1]=dp[u][0],dp[u][0]=make_pair(dp[v][0].first+1,v);
                else if(dp[v][0].first+1>dp[u][1].first)
                    dp[u][2]=dp[u][1],dp[u][1]=make_pair(dp[v][0].first+1,v);
                else dp[u][2]=max(dp[u][2],make_pair(dp[v][0].first+1,v));
            }
        }
        inline void Dp2(int u,int fa){
            for(auto v:G[u])if(v!=fa)
                if(dp[u][0]==make_pair(dp[v][0].first+1,v))df[v]=dp[u][1].first;
                else df[v]=dp[u][0].first;
            int mx=dp[u][0].first,se=dp[u][1].first;
            if(a[u])dq[u]=max(dq[u],0);
            if(mx<dq[u])se=mx,mx=dq[u];
            else se=max(se,dq[u]);
            for(auto v:G[u])if(v!=fa){
                if(mx==dp[v][0].first+1)dq[v]=se+1;
                else dq[v]=mx+1;
                Dp2(v,u);
            }
        }
        inline void init(){
            Dp1(1,0),Dp2(1,0);
            for(int i=1;i<=n;++i)ST[0][dL[i]]=df[i];
            for(int j=0,jj=1;jj<=n;++j,jj*=2)
                for(int i=n-jj*2+1;i>=1;--i)
                    ST[j+1][i]=max(ST[j][i],ST[j][i+jj]);
        }
        inline int qry(int l,int r){
            if(l>r)return -INF;
            const int t=__lg(r-l+1);
            return max(ST[t][l],ST[t][r-(1<<t)+1]);
        }
        inline int solve(int u,int v){
            if(u==v)return max(dp[u][0].first,dq[u])*2;
            int bas=dist(u,v);
            if(dL[u]>dL[v])swap(u,v);
            if(dL[u]<=dL[v]&&dL[v]<=dR[u]){
                int ans=0;
                for(;d[top[v]]>=d[u]+1;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
                if(d[u]+1<=d[v])ans=max(ans,qry(dL[top[v]]+d[u]-d[top[v]]+1,dL[v]));
                ans=max(ans,dq[u]);
                return ans*2+bas;
            }
            int ans=max(dp[u][0].first,dp[v][0].first),p=LCA(u,v);
            for(;d[top[u]]>=d[p]+2;u=f[top[u]])ans=max(ans,qry(dL[top[u]],dL[u]));
            if(d[p]+2<=d[u])ans=max(ans,qry(dL[top[u]]+d[p]-d[top[u]]+2,dL[u]));
            for(;d[top[v]]>=d[p]+2;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
            if(d[p]+2<=d[v])ans=max(ans,qry(dL[top[v]]+d[p]-d[top[v]]+2,dL[v]));
            if(d[top[u]]>d[p]+1)u=f[top[u]];else u=rk[dL[top[u]]+d[p]-d[top[u]]+1];
            if(d[top[v]]>d[p]+1)v=f[top[v]];else v=rk[dL[top[v]]+d[p]-d[top[v]]+1];
            if(dp[p][0].second!=u&&dp[p][0].second!=v)ans=max(ans,dp[p][0].first);
            else if(dp[p][1].second!=u&&dp[p][1].second!=v)ans=max(ans,dp[p][1].first);
            else ans=max(ans,dp[p][2].first);
            ans=max(ans,dq[p]);
            return ans*2+bas;
        }
    }T,H;
    inline void dfs(int u,int fa,int k){
        if(G[u].size()==1)bl[u]=k;
        for(auto v:G[u])if(v!=fa)dfs(v,u,k);
    }
    inline void Dp1(int u,int fa){
        if(bl[u])dp[u].first=u;
        for(auto v:G[u])if(v!=fa){
            Dp1(v,u);
            auto [a,b]=dp[u];auto [c,d]=dp[v];
            if(c&&(!a||dist(a,u)<dist(c,u)))swap(a,c);
            if(d&&(!a||dist(a,u)<dist(d,u)))swap(a,d);
            if(c&&(!b||dist(b,u)<dist(c,u)))swap(b,c);
            if(d&&(!b||dist(b,u)<dist(d,u)))swap(b,d);
            if(d&&(!c||dist(c,u)<dist(d,u)))swap(c,d);
            dp[u].first=a;
            if(b&&bl[a]!=bl[b])dp[u].second=b;
            else if(c&&bl[a]!=bl[c])dp[u].second=c;
            else if(d&&bl[a]!=bl[d])dp[u].second=d;
        }
    }
    inline void Dp2(int u,int fa){
        for(auto v:G[u])if(v!=fa){
            auto [a,b]=dp[u];auto [c,d]=dp[v];
            if(c&&(!a||dist(a,v)<dist(c,v)))swap(a,c);
            if(d&&(!a||dist(a,v)<dist(d,v)))swap(a,d);
            if(c&&(!b||dist(b,v)<dist(c,v)))swap(b,c);
            if(d&&(!b||dist(b,v)<dist(d,v)))swap(b,d);
            if(d&&(!c||dist(c,v)<dist(d,v)))swap(c,d);
            dp[v].first=a;
            if(b&&bl[a]!=bl[b])dp[v].second=b;
            else if(c&&bl[a]!=bl[c])dp[v].second=c;
            else if(d&&bl[a]!=bl[d])dp[v].second=d;
            Dp2(v,u);
        }
    }
    inline void build(){
        dfs1(1,0),dfs2(1,0,1);
        int rtx=1,rty=1,rt=0;
        for(int i=1;i<=n;++i)if(d[i]>d[rtx])rtx=i;
        for(int i=1;i<=n;++i)if(dist(rtx,i)>dist(rtx,rty))rty=i;
        if(d[rtx]>d[rty])swap(rtx,rty);
        D=dist(rtx,rty),rt=rty;
        for(int i=0;i<D/2;++i)rt=f[rt];
        if(D&1)dfs(rt,f[rt],++cnt),dfs(f[rt],rt,++cnt);
        else for(auto v:G[rt])dfs(v,rt,++cnt);
        Dp1(1,0),Dp2(1,0);
        for(int i=1;i<=n;++i)H.a[i]=1,T.a[i]=bl[i];
        H.d=d,H.dL=dL,H.dR=dR,H.G=G,H.n=n,H.rk=rk,H.sz=sz,H.top=top,H.f=f;
        T.d=d,T.dL=dL,T.dR=dR,T.G=G,T.n=n,T.rk=rk,T.sz=sz,T.top=top,T.f=f;
        H.init(),T.init();
    }
    inline int solve(int u,int v,int L){
        if(H.solve(u,v)>=L)return 2;
        const auto [a,b]=dp[u];const auto [c,d]=dp[v];
        int sa=max(dist(u,a)+H.solve(a,v),H.solve(u,c)+dist(c,v)),sb=T.solve(u,v);
        return min(max(0,(L-sa+D+D-1)/(D+D)*2)+3,max(0,(L-sb+D+D-1)/(D+D)*2)+2);
    }
}T1,T2;
int n,m,q;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    T1.init(n);
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        T1.add(u,v);
    }
    T2.init(m);
    for(int i=1;i<m;++i){
        int u,v;cin>>u>>v;
        T2.add(u,v);
    }
    if(min(n,m)<2){
        for(int i=1;i<=q;++i){
            int u,x,v,y;cin>>u>>x>>v>>y;
            if(u==v&&x==y)cout<<"0\n";
            else cout<<"-1\n";
        }
        return 0;
    }
    T1.build();
    T2.build();
    for(int i=1;i<=q;++i){
        int u,x,v,y;cin>>u>>x>>v>>y;
        int duv=T1.dist(u,v),dxy=T2.dist(x,y);
        if(duv==dxy)cout<<min(duv,1)<<'\n';
        else if(duv%2!=dxy%2)cout<<"-1\n";
        else if(duv<dxy)cout<<T1.solve(u,v,dxy)<<'\n';
        else cout<<T2.solve(x,y,duv)<<'\n';
    }
    return 0;
}
/*
21 56 1
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
19 1 19 51
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 73728kb

input:

4 5 7
1 2
2 3
2 4
1 2
2 3
3 4
4 5
1 1 2 5
1 5 4 1
1 5 4 2
2 5 2 3
2 1 2 5
3 2 3 2
4 4 1 2

output:

-1
2
-1
2
3
0
1

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 4ms
memory: 45068kb

input:

1 3 4
1 2
2 3
1 1 1 1
1 2 1 2
1 2 1 3
1 1 1 3

output:

0
0
-1
-1

result:

ok 4 number(s): "0 0 -1 -1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 71640kb

input:

6 2 18
1 2
2 3
3 4
4 5
5 6
1 2
1 1 1 2
1 1 2 2
1 1 3 2
1 1 4 2
1 1 5 2
1 1 6 2
1 1 1 1
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 6 1
1 2 1 2
1 2 2 2
1 2 3 2
1 2 4 2
1 2 5 2
1 2 6 2

output:

-1
1
-1
3
-1
5
0
-1
2
-1
4
-1
0
-1
2
-1
4
-1

result:

ok 18 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 79812kb

input:

21 65 8
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
...

output:

6
6
5
5
6
6
5
5

result:

ok 8 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 79864kb

input:

10 15 10
9 10
9 3
8 3
4 8
1 4
1 6
4 5
7 5
1 2
8 9
9 10
10 2
15 2
5 15
5 1
1 3
3 13
4 13
11 4
1 6
6 14
7 6
12 7
8 12 2 7
6 14 1 11
1 6 7 5
5 2 5 11
3 13 8 10
5 6 7 6
7 11 10 11
8 1 6 6
10 11 2 13
6 10 7 12

output:

2
-1
-1
-1
-1
-1
2
2
2
-1

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 40984kb

input:

1 15 10
14 2
14 15
13 15
5 13
8 5
8 4
4 7
9 7
11 9
11 3
4 6
10 13
10 1
12 8
1 6 1 7
1 6 1 12
1 2 1 12
1 3 1 8
1 8 1 10
1 12 1 2
1 4 1 5
1 12 1 10
1 3 1 3
1 12 1 9

output:

-1
-1
-1
-1
-1
-1
-1
-1
0
-1

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 4ms
memory: 40984kb

input:

1 1 10
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 40980kb

input:

25 1 10
12 3
3 25
4 25
8 4
8 9
9 18
18 6
24 6
24 1
11 1
2 9
6 5
15 5
15 7
25 21
16 21
14 1
23 2
23 19
19 10
22 8
13 22
20 13
17 8
1 1 21 1
3 1 2 1
18 1 13 1
7 1 3 1
20 1 11 1
7 1 13 1
18 1 5 1
16 1 1 1
2 1 22 1
24 1 16 1

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 75800kb

input:

14 15 30
3 5
8 5
7 8
7 4
4 13
13 11
11 14
14 10
12 4
12 1
2 13
6 2
9 6
3 12
7 3
7 11
11 10
9 10
9 6
3 5
14 9
2 3
7 1
10 4
4 15
13 10
1 8
14 2 12 6
2 14 1 8
8 4 14 11
3 14 5 3
7 10 6 11
11 9 6 10
13 4 6 5
12 3 14 3
5 6 12 11
2 4 6 8
11 12 6 4
2 13 8 11
2 4 2 12
12 6 8 15
3 11 5 12
9 3 2 14
2 11 1 8
8...

output:

2
2
-1
2
-1
2
-1
2
-1
2
2
2
-1
-1
2
-1
-1
-1
2
-1
2
-1
-1
-1
2
-1
-1
2
-1
-1

result:

ok 30 numbers

Test #10:

score: 0
Accepted
time: 3ms
memory: 75864kb

input:

14 15 30
14 1
7 1
7 2
6 2
8 6
8 13
10 13
2 3
5 3
8 4
3 12
11 7
1 9
7 15
7 1
4 1
3 4
3 13
2 13
2 14
8 4
6 8
12 6
3 9
5 9
4 11
11 10
13 8 2 2
1 15 6 7
10 9 9 1
12 6 13 15
6 13 3 12
8 3 2 9
11 2 14 5
8 7 8 5
2 1 6 1
9 12 7 5
3 13 3 12
11 4 7 4
11 8 10 1
11 1 6 2
9 8 2 12
4 9 5 7
9 12 7 6
14 2 2 2
6 3 6...

output:

-1
2
2
1
-1
-1
-1
-1
-1
2
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
2
1
2
-1
-1
1
-1
-1
2
2

result:

ok 30 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 73720kb

input:

20 15 30
16 19
19 14
3 14
1 3
20 1
17 20
1 18
9 3
9 10
15 10
9 7
12 14
5 12
11 20
4 7
2 3
13 3
19 6
8 1
4 15
15 6
12 6
12 10
2 10
5 2
5 13
1 5
10 9
11 9
12 3
3 8
8 7
14 10
1 10 11 3
1 5 2 7
17 8 10 10
10 12 16 6
11 3 7 9
19 13 6 13
10 2 17 12
14 10 13 15
20 5 9 10
3 8 10 12
6 14 17 13
13 8 3 2
3 6 8...

output:

1
2
2
2
2
-1
-1
-1
-1
1
2
-1
-1
2
2
2
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1

result:

ok 30 numbers

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 73736kb

input:

20 15 30
14 1
14 18
9 18
6 9
2 6
2 10
10 17
11 9
2 16
5 14
10 8
11 20
20 19
3 14
18 7
13 7
15 2
15 12
4 6
13 11
9 13
8 9
15 8
15 7
7 14
14 3
3 10
6 14
9 12
12 1
6 4
2 9
5 14
17 8 14 6
15 10 9 1
4 11 4 1
6 15 18 1
3 1 5 1
9 1 14 4
16 3 12 7
14 2 13 11
7 14 4 4
3 12 1 15
20 15 4 3
14 9 1 13
14 13 4 11...

output:

2
-1
2
2
2
3
-1
1
2
-1
-1
1
-1
2
-1
1
1
-1
2
2
-1
2
2
2
2
-1
-1
2
2
2

result:

wrong answer 6th numbers differ - expected: '2', found: '3'