bzoj 4568 洛谷 3292 libreoj 2013 [SCOI2016]幸运数字 题解

发表于 | 更新于 | 阅读次数：
本文字数： 933 字 | 阅读时长 ≈ 5 分钟

题意简述

给定一颗$n<=20000$个点的树，点带点权，不超过$2^{60}$。还有$Q<=200000$个询问，每次询问两个点之间路径上的最大异或和。

思路

$B[i][k]$表示从$i$往上$2^k$个节点组成的线性基。$LCA$的时候线性基合并就珂以了。带三个log，两个是$log2^{60}$，一个是$logn$。也就是$O(200000\times 60\times 60\times 16)$。虽然看起来有$1e9$，但是你相信我那两个$60$乘不满。所以你能过。在$bzoj$的机器上写面向对象都能过。

代码细节

这题重在模拟。代码细节蛮多的。

  1. lca的第一步，跳到同一高度，判断条件是deep[fa[u][k]]<=deep[v]
  2. lca的最后一步，要把val[u],val[v],val[fa[u][0]]的值都插入进来。联想一下求最小值你就明白这步了
  3. 好像没了？代码还是蛮长的，别写挂别的地方即珂

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 24444
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    class LB
    {
    public:
        int d[64];
        int& operator[](int id){return *(d+id);}
        void Init(){FK(d);}
        void Insert(int x)
        {
            D(i,60,0)
            {
                if (!(x&(1ll<<i))) continue;

                if (!d[i])
                {
                    d[i]=x;break;
                }
                x^=d[i];
            }
        }
        int MaxXor()
        {
            int ans=0;
            D(i,60,0) if ((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
    LB Merge(LB a,LB b)
    {
        D(i,60,0)
        {
            if (b[i]) a.Insert(b[i]);
        }
        return a;
    }
    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,m;int val[N];
    void Input()
    {
        R1(n),R1(m);
        F(i,1,n) R1(val[i]);
        G.clear();
        F(i,1,n-1)
        {
            int u,v;R1(u),R1(v);
            G.Add2(u,v);
        }
    }

    LB B[N][18];
    int fa[N][24],deep[N];
    void DFS(int u,int f)
    {
        deep[u]=deep[f]+1;
        fa[u][0]=f;
        B[u][0].Init();B[u][0].Insert(val[u]);
        F(i,1,16)
        {
            fa[u][i]=fa[fa[u][i-1]][i-1];
            B[u][i]=Merge(B[u][i-1],B[fa[u][i-1]][i-1]);
        }
        
        Tra(i,u)
        {int v=__v;
            if (v==f) continue;
            DFS(v,u);
        }
    }

    int LCA(int u,int v)
    {
        LB ans;ans.Init();
        if (deep[u]<deep[v]) swap(u,v);
        D(i,16,0)
        {
            if (deep[fa[u][i]]>=deep[v]) 
            {
                ans=Merge(ans,B[u][i]);
                u=fa[u][i];
            }
        } 

        if (u==v)
        {
            ans.Insert(val[u]);
            return ans.MaxXor();
        }

        D(i,16,0)
        {
            if (fa[u][i]!=fa[v][i])
            {
                ans=Merge(ans,B[u][i]);
                ans=Merge(ans,B[v][i]);
                u=fa[u][i],v=fa[v][i];
            }
        }
        ans.Insert(val[u]);ans.Insert(val[v]);
        ans.Insert(val[fa[u][0]]);
        return ans.MaxXor();
    }
    void Soviet()
    {
        DFS(1,1);

        F(i,1,m)
        {
            int u,v;R1(u),R1(v);
            printf("%lld\n",LCA(u,v));
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w