noi.ac 41 最短路 题解

发表于 | 阅读次数：
本文字数： 1.2k 字 | 阅读时长 ≈ 5 分钟

题意简述

给你一个 $n$ 个点的边带权的树，还有 $m$ 个新增的修建计划，以及 $Q$ 个询问。每一个询问的格式是：给定 $s,t,l,r$ ，问你，如果动用 $[l,r]$ 之间的修建计划，从 $s$ 到 $t$ 的路径中，边权异或和最小是多少？

询问之间是独立的，在某一个询问里加入的修建计划，询问完就会拆掉。并且修建计划保证不是树上原来就有的边。

$n,m,q\le 3\times 10^5$，所有的边权（树上和修建计划） $\le 10^9$。对于每个询问，$1\le s,t\le n$，并且$1\le l\le r\le m$。

思路

由 bzoj 2115 的结论得，一张图上从 $s$ 到 $t$ 的路径的异或和，可以由另外一条路径的异或和，异或上几个环的异或和得到。

然后我们珂以先取初始值为 $s$ 到 $t$ 树上路径的异或和，然后在把所有环的异或和放到线性基里，求最小异或和。

本题还限制了只能动用 $[l,r]$ 之间的修建计划。那就按 $r$ 排个序，对于每个位置 $i$ ，记录所有 $r=i$ 的询问。然后在插入线性基的时候，顺便维护上修建计划的编号。对于每个询问，我们只考虑 $[1,r]$ 的修建计划，不用考虑动用 $>r $的修建计划的问题，只要满足修建计划的编号 $\ge l$ 即珂。线性基求最小异或和的时候，顺便维护下即珂。

代码

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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 355555
    #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 MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    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;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    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;
    
    int n,m,q;
    void Input()
    {
        Rd(3,&n,&m,&q);
        G.clear();
        F(i,1,n-1) 
        {
            int u,v,w;Rd(3,&u,&v,&w);
            G.Add2(u,v,w);
        }
    }
    int d[N];
    void DFS(int u,int f) //先预处理出每个点到根的异或和：d[i]
    {
        Tra(i,u)
        {int v=__v;
            if (v!=f)
            {
                d[v]=d[u]^G.Label(i);
                DFS(v,u);
            }
        }
    }
    int w[N];
    int l[N],r[N];
    int p[32],id[32]; //p是线性基，id是线性基顺便维护的修建计划编号
    vector<int> pos[N];
    int ans[N];
    void Soviet()
    {
        DFS(1,1);
        F(i,1,m) 
        {
            int u,v,len;Rd(3,&u,&v,&len);
            w[i]=d[u]^d[v]^len; //第i个修建计划从u到v，那就会产生一个环，这个环的异或和为：u到v树上路径的异或和，再以后上修建计划的边权
        }
        F(i,1,q) 
        {
            int s,t;Rd(2,&s,&t);
            ans[i]=d[s]^d[t]; //初始答案就是s到t的树上路径异或
            Rd(2,&l[i],&r[i]); 
            pos[r[i]].p_b(i); //离线，按r排序，把r相同的询问一块考虑
        }
        F(t,1,m)
        {
            int x=w[t],r=t;
            D(i,30,0) if ((x>>i)&1) 
            {
                if (!p[i]){p[i]=x;id[i]=r;break;}
                if (id[i]<r) swap(p[i],x),swap(id[i],r);
                x^=p[i];
            } //插入线性基的时候顺便维护编号
            F(k,0,sz(pos[t])-1)
            {int v=pos[t][k];
                D(i,30,0)
                {
                    if (id[i]>=l[v]) ans[v]=min(ans[v],ans[v]^p[i]);
                 //在考虑编号>=l的情况下，求最小异或和
                }
            }
        }
        F(i,1,q) printf("%d\n",ans[i]);
    }

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