NOI结束以后一直没有更过博客..主要原因是没有系统的做过题..整天在家里看看番玩玩galgame..彻底进入了AFO状态..

最近几天也是感觉这样太颓了..就试着去写了些CF和TC最近的题目..发现根本不会做..

感觉今年多校的题还是挺和谐的..就试着补一补当做康复训练吧..

[upd 8.20]七夕佳节，2015多校总是告一段落了。最后的最后学车中学总算是极限逆二了，一方面感觉也是挺可惜的，如果多打一场就可以轻松一位了；又一方面感觉也是真不容易啊，NOI之后本来就没有几个人打了高二那帮人还被拉去北大队打了，这七场基本都是只有两个人打，最后能打到第二当初真的没想到。鏼鏼鏼、松爷、杜爷、皮球老司机还有时不时蹦出来秒题的DZY真是业界良心ww

[upd 9.10]姑且先算是完结了吧，整个多校2015现在还有2题我没有写过代码，一题是X大爷的神题+码农提..一题是绍一的码农线段树题..这两题实在是懒（bu）得（hui）写..所以还是弃坑吧..总之还是撒一下花。

现在做了几题

【#1】OO’s Sequence 比赛的时候做的，容斥随便搞搞就好了。

【#1】Assignment 比赛的时候做的，从小到大枚举最大值，然后二分一下左右端点统计答案。

【#1】Bombing plan 令[tex]f_{i,j}[/tex]表示以[tex]i[/tex]为根的子树中，把从[tex]i[/tex]的第[tex]j[/tex]代子孙开始所有的节点都覆盖的最小数目，[tex]g_{i,j}[/tex]表示把[tex]i[/tex]子树节点都覆盖的情况下，还能覆盖到[tex]i[/tex]的第[tex]j[/tex]个祖先的最小数目，直接DP就行了。

【#1】Candy Distribution 比赛的时候做的，分奇偶性讨论一下记两个值就可以把DP的转移优化掉..

【#1】Pocket Cube 结论题..只可惜我们队一个玩魔方的人都没有..搞了两个多小时的爆搜没搞出来..结论一句话说不清楚就不说了..

【#1】Tree chain problem 比赛的时候做的，和去年多校的题目很像，把每一条链标记到它两个端点的LCA上，令[tex]dp_i[/tex]为只考虑这个子树以及在这个子树中的链的最优值，然后可以列出一个DP式子，用树状数组优化一下就好了。

【#1】Tricks Device 比赛的时候做的，题意很感人..揣测了半天终于猜对了..样例和没给一样..具体是什么题意我已经忘了..

【#1】Unstable 计算几何题..感觉水平有点高啊..先倍长AF至A'，然后三角形A'BC的三边确定。然后作BG平行等于CA，那么三角形GCD三边确定。直接解两个三角形得到第三个点的坐标就好了。问题就变成了求两个圆的交点。试着写了一下WC的时候讲的方法..感觉误差略大但是居然还是过了。

【#1】Annoying problem 做过太多遍了..就不写了..直接set维护一下关键点的DFS序的相对顺序就好了。

【#1】Y sequence 二分一下答案，然后随便容斥一下..似乎卡了一波常数..懒得打表了就当过了吧。

【#1】Solid Geometry Homework 去膜了题解..感觉和CF的一道div1A很像..每一个点和每一个平面/圆有一个位置关系，两个点的颜色不同当且仅当它们的位置关系有奇数个不同。这样就可以直接搞了。

【#1】Circles Game 扫描线，维护当前每一个圆和扫描线交点的相对顺序，因为圆不相交，所以不存在相对顺序发生变化的情况，就可以直接用set维护了，这样就可以建出包含关系树，之后就是经典的博弈问题了。

【#2】Buildings 这题是我们以前一套CF的div1A，把删除点到四个边界的距离以及[tex]\lfloor \frac{n+1}{2} \rfloor[/tex]、[tex]\lfloor \frac{m+1}{2} \rfloor[/tex]搞搞minmax就好了。

【#2】Connect the Graph 这题本来是X大爷出的CF的div1 B，不过加上了三个值都大于等于1的条件之后简单了好多..对于每一个大小大于等于5的环构造一个黑边的圈和白边的圈然后删掉一些就好了。因为有那个大于等于1的条件所以两个圈有一条边共用没有什么关系。

【#2】Delicious Apples 鏼鏼鏼的普及组模拟题..听说正好压中了IOI题..因为有总和不超过[tex]10^5[/tex]的条件所以很方便..排序后枚举前多少个苹果是顺时针拿的，中间是否有[tex]k[/tex]个苹果是直接绕整圈拿的。然后对于半边就直接DP预处理一下就好了。

【#2】Eastest Magical Day Seep Group's Summer 这题本来是我和DZY合出的基环外向树BC专场的C，枚举基环外向树的环的点集然后把环缩起来跑基尔霍夫矩阵就行了。统计环的方案数直接DP就好了。

【#2】Friends X大爷出的签到题..每一个点的最后一条边的状态确定，且每一个点的度数一定是偶数，所以最多只需要搜20条边。直接暴力就好了。

【#2】Gorgeous Sequence X大爷出的CF的div1 E，线段树神题..其实也说不上太难，维护标记使得满足一个节点的标记值严格大于他子树中的标记值。然后对于每一个标记记录子树中等于它的叶子有多少个，这样就可以查询和了。然后在修改的时候DFS清空标记值不小于它的标记。清空的复杂度是等于打标记的复杂度，我写程序的时候直接标记永久化了。

【#2】He is Flying X大爷出的，把每一条线段的起点终点拆开来，可以转成FFT。开始以为这么大浮点数的FFT会炸，验题的时候我还码了一个crt，然而浮点数的FFT并不会炸..

【#2】I Wanna Become A 24-Point Master 我出的傻逼题，然而spj写错了..[tex]n[/tex]很大的时候可以由固定的式子得到答案，[tex]n[/tex]小的时候就搜一搜或者手算打打表就好了。

【#2】 JRY is Fighting DZY出的div1 C，感觉还是有点难度的..先用单调栈预处理出在每一个点磕了药最多可以走多远。然后有一个[tex]n^2[/tex]的DP可以求出来在每一个节点嗑药后走到终点的最大间隔。在这个DP中每一个节点[tex]j[/tex]对[tex]i[/tex]的贡献是[tex]\min(j-i,f_j)[/tex]，前一部分的选择是单调的，直接扫过来，后一部分用堆维护。然后求出这个值后贪心的求方案就好了。

【#3】Magician 傻逼线段树..样例给的太坑题意各种看不懂..

【#3】RGCDQ 比赛的时候做的，[tex]F_i[/tex]的最大值很小，直接预处理一下所有数的函数值然后求一下前缀和暴力枚举两个函数值就好了。

【#3】The Goddess Of The Moon 比赛的时候做的，起始求的就是一张无向图长度为[tex]m[/tex]的路径条数，随便矩乘一下就好了。唯一的坑点在于相同的数值要并到一起，是算成同一个点的。

【#3】Painter 比赛的时候做的，开始鏼鏼鏼先开这题，然后他以为是网络流就弃了..题目把每种颜色的方向都指出了只要直接模拟就行了。

【#3】Fan Li 傻逼代码题..把同一个左端点gcd相同的区间给并到一起。然后枚举gcd的值，把满足的区间的段给拿出来一起处理。离散化之后树状数组搞搞就好了。

【#3】Beautiful Set 比赛的时候做的，就是花样反演..值得注意的是数列中每一个自然数的倍数的个数的总和是[tex]O(n \log n)[/tex]的，所以在计算一个式子的时候可以直接暴力。

【#3】Hope 比赛的时候做的，分治FFT裸题。随便搞出一个DP式子然后就可以用FFT优化了。比赛结束后听fancy说OEIS上有？真是日了狗了。

【#3】Solve this interesting problem 比赛的时候做的，每一个区间的父节点至多有四种情况，直接暴力枚举，因为父节点的区间长度是子区间的两倍，所以判一下边界复杂度大约是[tex]2015^2[/tex]。

【#3】Boring Class 比赛的时候做的，和名字一样，非常无聊的一道题。就是二维数点卡了一卡空间，直接分治一下树状数组就好了。

【#3】Crazy Bobo 显然选出来的子图满足：以权值最小的节点为根，所有节点的权值都比它的父节点大。所以只需要按照权值排序一个一个插入就好了。

【#3】Work 比赛的时候做的，大暴力签到题。

【#4】Olympiad 比赛前临时加的签到题，直接暴力就好了。本来一直建议XYZ把区间的范围改到[tex]10^{10^5}[/tex]然而他并不听我的QWQ

【#4】Problem Killer 比赛前临时加的签到题，每一个节点记录它往前两种序列最长长度，递推就好了。

【#4】Question for the Leader 这题本来是我和DZY合出的基环外向树BC专场的D，如果是树的话枚举[tex]n[/tex]的约数，然后对于每一个子树大小为枚举数的倍数的节点割掉它和它父亲的边，判断一下割了多少条边就好了。至于奇环外向树就把外向的树全都用这种方法判断，然后到了环上就根据枚举数的约数来判断割哪一组的边，如果存在合法的约数就累加答案。

【#4】Route Statistics 听说类似的思路X大爷出到过他的提高组模拟题里？DP，大致的思路就是DP出对每一个可能的坐标，与它距离为[tex]j[/tex]的关键点有多少个。DP方程大约是[tex]dp_{i,j,k}[/tex]为考虑[tex]i[/tex]这个坐标，前[tex]j[/tex]位和它一样的关键点中和它距离为[tex]k[/tex]的有多少个。转移还是挺显然的就不多说了。

【#4】Simple Problem 我出一道防AK题..然而场上还是被sone爷直接艹了..大致的思路就是把独立集转化为匹配然后在DP式子上找一点性质来维护。本来感觉挺难的，标的是hard，然而杜爷在验题的时候被贪心直接切了，于是就标回medium-hard了。至于是什么贪心因为我自己也不怎么明白就不说了。

【#4】Test for Rikka 本来是我出到我们CF的div1 D，后来送给XYZ当他的div1 D，最后又变成多校了。感觉还是挺有趣的，出题的时候想了一个又一个的图来压节点数。思路很简单就是进制拆分，难点在于用的不是惯性思维的DAG来搞进制而是用完全图利用步数来拆进制。

【#4】Undirected Graph 本来我想出一道傻逼分块代码题，然后就出了这么个题。然而杜爷验题的时候直接用LCT切了..于是就压了压时限变成[tex]O(n \log n)[/tex]咯。把每一条边的权值标为两端点编号的较大值，然后把询问离线，从小到大枚举右端点，把边插进来，然后维护最大生成树。每一组询问相当于询问最大生成树中权值大于等于某个数的边有多少个，用树状数组搞搞就好了。

【#4】Virtual Participation 我出的div1 B，感觉还是挺有趣的，有很多做法。我的做法就是把每一个相同的数值放到连续的一段来构造，直接找到一个条件很松的方程组的一组解就好了。然而我傻逼把spj写错了，树状数组忘记清空了..我的锅，对不起参赛的人QWQ

【#4】Walk Out XYZ的div 1A，把和左上角联通的所有0缩到一起，然后找到距离终点最近的节点集合，贪心的走每一步就好了。

【#4】XYZ and Drops 松爷出的大模拟，本来数据范围是[tex]10^5[/tex]，我当成消棋子用STL大法随便写了一发，后来发现可以被卡到[tex]O(n \sqrt n \log n)[/tex]，然后听说松爷的标算复杂度是对的..然而一直不知道正确的姿势，最后因为要把难度给压下来所以把数据范围改到了100。

【#4】Yet Another XYZ Problem XYZ出的报复社会分类讨论题..长的和一道TC题很像然而做法完全不同..做法也没什么好说的，就是分类讨论..每一种情况推一个式子啥的。

【#4】ZZX and Permutations 鏼出的挺有意思的题目，总之就是贪心，每一次给当前最小的还没有确定的坐标找一个尽可能大的数替换上来。用线段树+set搞搞就行了。

【#5】MZL's Circle Zhou 果然边看好呻吟边写题就会被打debuff..题目还是不难的..先对第二个串预处理出以第[tex]i[/tex]个字符开头的本质不同的字符串个数，这个在SAM上递推一下就好了。然后对第一个串做后缀自动机，每一个节点的贡献是匹配到这个节点的串的个数（即t[i].val-t[t[i].father].val）乘上以每一个它不存在出边的字符开头的在第二个串中的不同子串个数之和，累加一下就好了。注意答案会爆long long，用unsigned就好了。

【#5】MZL's xor 本来以为是tyvj月赛的那道神题..然而忘了怎么做了..想了很久之后一看玛雅比赛的时候有600+队伍AC，然后发现果然是看错题咯。[tex]i \neq j[/tex]的时候会算两遍贡献为0，所以答案就是每一个数字乘二然后异或起来。

【#5】MZL's combat hdu上只有两人AC的多校题之前见过的只有Angry Tree一道..所以吓得我看完题面就去看题解了。感觉我这种只有普及组博弈水平的人肯定也想不出来..每一个白点都是独立的，sg值为[tex]\text{lowbit} (\max (x,y))[/tex]，所以只要求矩形并的所有节点的sg值的异或值就好了..然后我发现我不会求矩形并咯..脑补了好长时间发现似乎标记永久化就好了..然后居然过了样例就1A了真是奇迹..不知道为什么通过的人那么少

【#5】MZL's game 感觉是一道好题目..然而现场AC人数直接把我吓得去看题解咯（然而根本看不懂绍一哒哒们写的题解）..因为每一个人都是等价的，我们考虑按照编号1到[tex]n[/tex]的顺序选人，令[tex]dp_{i,j}[/tex]表示选到了第[tex]i[/tex]个人，[tex]i[/tex]到[tex]n[/tex]已经被攻击了[tex]j[/tex]次的概率，然后就可以[tex]O(1)[/tex]转移咯。

【#5】MZL's chemistry 虽说现在已经变成化学战五渣了但是至少这种题还是会做的..大致上是同一周期递增同一族递减，要注意s2，s2p3类型的电子排布的第一电离能是比下一个大的。

【#5】MZL's endless loop 虽然这题出的并不差..但是还是好想说一句“瘠薄题目毁我青春”..虽然开始想到了标算，但是感觉懒得写..然后搞了几个好写的乱搞之后还是不得不写标算去了..然后各种细节写残各种WA..感觉没有什么救了。

【#5】MZL's simple problem 签到题，维护一下最大值和元素个数就好了。

【#5】MZL's munhaff function 虽然开始也感觉题目怎么那么像huffman，但是智商比较低完全没有发现答案就是哈弗曼树啊..只想到了一个[tex]O(n \log n)[/tex]的傻逼做法而且不知道对不对..upd：刚才YY了一下发现是错的

【#5】MZL's Border 找规律题..感觉还是不难找的，如果[tex]fib_i[/tex]是第一个长度超过询问长度加一的，那么答案就是[tex]m-|fib_{i-2}|[/tex]。

【#5】MZL's City 匈牙利算法的小拓展，要求字典序最小，因为匈牙利算法已经匹配完的节点流量是不会变的，所以直接倒过来做就好了。

【#6】Average 比赛的时候做的，分类讨论题，减去平均数之后每一个节点的值只可能在-2到2之间，如果有2就直接从2出去贪心的分配，有-2就从-2开始贪心的分配然后再倒过来，否则就贪心的绕一圈把1和-1配对。听说数据很弱我也不知道我的算法对不对。

【#6】Bipartite Graph 动态插入一条边，判断是不是二分图，这个可以用并查集来实现。所以这儿只需要分治一下，然后套个按秩合并的并查集就好了。这题居然没有卡常数感觉很不科学。

【#6】Cake 才发现考场上写的程序是错的..去膜了一下题解..无解的条件是和不是[tex]m[/tex]的倍数或者平均数比[tex]n[/tex]小。当[tex]n[/tex]很大的时候，可以从[tex]n[/tex]中拿出最后[tex]2m[/tex]个数配成相等。最后剩下来的数搜索一下方案。加一下剪枝和记忆化就能过了。

【#6】Deal 比赛的时候做，每一种颜色显然是独立的，然后猜了一下感觉每一步肯定都是贪心的走最远距离的点，所以只需要预处理一下最深的深度排序一下搞一搞就好了。然后最后的答案就是一个[tex]n[/tex]路归并。出题人常数卡的非常厉害...卡了半天才卡过去。

【#6】Easy Sequence 常数卡的好..我选择死亡..大致就是先处理出前缀和，然后在求出每一个位置作为右端点是否有括号序列，如果有，第一个左端点是什么。这个桶排之后链表搞搞就好了。最后再前缀和扫一遍处理出[tex]ans[/tex]再累加起来即可..这个题面写的真恶心。

【#6】First One 枚举一下左端点，然后枚举一下答案，显然右端点是单调的，所以搞一个指针扫一下就好了。

【#6】Group 先把每一条边中间插上一个点，这样边问题就转化为了点问题。把每一个强连通分量分来开考虑，随便选一个非边节点当源，这张图的dominator tree中的所有非叶子节点都满足条件，然后再把所有边反向再做一遍就好了。

【#6】Hiking 比赛的时候做的，每一次把当前满足左半边条件的人给丢进堆里，然后取出右端点最小的来判断，扫一下就好了。

【#6】In Touch 比赛的时候做的，拿个堆拿个set模拟一下最短路就好了。

【#6】Just A String 比赛的时候做的令 [tex]dp_{i,j}[/tex]为[tex]i[/tex]个字符有[tex]j[/tex]种字符出现了奇数次，转移时[tex]O(1)[/tex]的，有点卡常数。

【#6】Key Set 比赛的时候做的，随便找找规律发现是[tex]2^{n-1}-1[/tex]。

【#7】Game On the Tree 比赛的时候做的，无聊代码题，贪心就好了。随便预处理一下搞得和度数无关就行了。

【#7】Tree Maker 一道挺有趣的题，杜爷现场1A实在太可怕..大致就是一个非常简单的区间DP，但是注意要充分利用每一种操作的特点，感觉还是挺容易漏掉一些DP的限制的。

【#7】Hotaru's problem 先manache求出每一个中间位置的回文半径，然后就只需要求最大的同时被两端覆盖的区间长度就好了，这个可以直接set扫一遍。

【#7】Segment Game 比赛的时候做的，因为插入的区间的长度是递增的，所以可以直接用当前左端点坐标大于等于这条线段的左端点坐标的线段数目减去右端点坐标大于这条线段的右端点坐标的线段数目。离散化一下直接树状数组就好了。

【#7】The shortest problem 位数最多也就200多万，预处理一下这个范围内每一个数的位数和数位和，就可以[tex]O(t)[/tex]了。

【#7】Tetris 比赛的时候做的，大模拟..不知道怎么回事调着调着就过了，总感觉样例有问题。

【#7】Gray code 比赛的时候做的，[tex]i[/tex]的格雷码就是[tex]i \otimes (i>>1)[/tex]，所以只要数位DP就好了。

【#7】Convex Polygon 挺有趣的题，但是我数学太差了，虽然想到了锐角个数不超过2但是没有发现是相邻的，所以一直没有推对式子。题解还是挺复杂的，还是推荐去看官方题解。

【#7】Root 直接BSGS时间复杂度是[tex]O(m \sqrt {sum})[/tex]，为了降低复杂度可以统一使用原根代替底数，这样预先在哈希表里插入的数就一样了，就可以选择插入[tex]O(\sqrt{m \times sum})[/tex]个数。在求答案的时候用扩展欧几里得解一个方程就好了，这样复杂度就变成了[tex]O(\sqrt{m \times sum})[/tex]

【#7】Leader in Tree Land 直接暴力DP的复杂度是[tex]O(n^2)[/tex]的，所以直接搞就好了。

【#7】Mahjong tree 比赛的时候做的，分别统计每一个节点的叶子节点和非叶子节点孩子数量，然后就可以直接计算了。

【#8】Travel with candy 比赛的时候做的，每一个点都可以用它当前最优的卖出价表示，然后维护一个单调栈贪心扫过去就好了。

【#8】The sum of gcd 傻逼数据结构题。

【#8】GCD?LCM! 先枚举GCD再枚举LCM，最后只需要对每一个数预处理它的质因数种类数就好了。

【#8】Yu-Gi-Oh! 比赛的时候做的，因为一共只有两类，所以就直接费用流。

【#8】Danganronpa 比赛的时候做的，开始把题目看反了，贴了一个后缀自动机上去，结果发现过不了样例..直接AC自动机就行了。

【#8】The path 只用考虑最短路径树就好了，所以可以从两端一个一个把节点插进去，然后按照插入的顺序定距离，树上的边权就是连接两点的距离差，非树边的边权就是[tex]n[/tex]。

【#8】Cover 直接从后往前贪，能选就选，一个操作能选的条件是还没有被覆盖的位置和最终状态的颜色一样。

【#8】Clock 算一下角度就行了。

【#8】Zero Escape [tex]i[/tex]的数字根是[tex](i-1)\% 9+1[/tex]，所以只要DP就好了。

【#8】tree 比赛的时候做的，卡空间卡的厉害，我直接预处理然后用trie套树状数组，写的意识模糊...赛后发现尼玛直接分块就能过..

【#9】Expression 挺简单的区间DP，直接枚举每一个区间里最后一个选取的符号然后分类讨论计算贡献就好了

【#9】Hack it! 有趣的题目，考虑加强题目的限制，即把两个串的长度限定为10000并分成2500个长度为4的小串，且限定每个小串都是()()或(())，那么题目就变成了有2500个权值，现在要给每一个权值乘上0或1或-1使得它们的和为0。因为数据时随机的，所以每次可以把最大的两个数拿出来相减并放去，直到出现两个相同的数为止，因为数据时随机的，所以跑得出来。

【#9】GCD Tree 脑补一下最小生成树的过程可以发现只需要保留每一个数连向它的约数的边就好了，所以就直接用LCT来维护最小生成树，一个一个点加进去就好了。

【#9】Too Simple 签到题，如果每一个给定串都合法（即都是排列），且存在[tex]k(k>0)[/tex]个-1，那么答案就是[tex](n!)^{k-1}[/tex]。如果没有-1就直接模拟一下就好了。

【#9】Arithmetic Sequence 签到题，直接预处理一下算一下就好了，注意特判两个公差一样的情况。

【#9】Persistent Link/cut Tree 大力出奇迹，直接记忆搜下去，复杂度似乎是靠谱的。

【#9】Travelling Salesman Problem 如果有一条边长度为奇数那么显然可以取完，如果有都是偶数，那么一定是删掉一个两维坐标之和为奇数的权值最小的格点，证明只要黑白染色一下就好了。构造的话就根据选取点两维坐标哪一维为奇数讨论一下就行了。

【#9】Goldbach's Conjecture 挺有趣的题，听说是论文题，大致就是如果[tex]m[/tex]为好数，那么[tex]nm(1 \leq n \leq 2m)[/tex]也一定是好数，如果预处理出一些[tex](m,m+2)[/tex]的好数对，就可以表示[tex][m^2+2,3m^2][/tex]的所有偶数。然后因为数据时随机的，所以怎么暴力怎么来就好了，找好数也可以直接随机的找，还是比较密集的。

【#9】Random Inversion Machine 一道很好玩的DP题，一句话不怎么说的清楚还是推荐杜爷的官方题解。

【#9】Sometimes Naive 直接强上树剖就好了。

【#10】CRB and Apple 比赛的时候做的，可以直接上费用流，因为流量只可能是2，但是这样会T，所以我的做法是直接先跑LIS然后建出增光之后的图，这样只用跑一遍spfa就好了。

【#10】CRB and Candies 比赛的时候做的，OEIS大法好，直接打了个表丢上去一搜，发现答案就是[tex]\frac{\text{lcm}(1,2,..,n+1)}{n+1}[/tex]，然后直接预处理出答案就好了。

【#10】CRB and Farm 在限制点的凸包里找一个点，然后从这个点出发向限制点的凸包顶点分别引射线，把外围和这些边有交的边的顶点都选出来，把那些点作为围栏的端点就行了。

【#10】CRB and Graph 就是求割边，然后如果以[tex]n[/tex]为根的话，那么答案就是子树最大值以及子树最大值加一。

【#10】CRB and His Birthday 比赛的时候做的，就是稍微变种一下的背包，随便DP一下就好了。

【#10】CRB and Puzzle 就是求一张无向图上长度小于等于给定值的路径条数，傻逼矩乘题。

【#10】CRB and Queries 比赛的时候做的，卡了一下空间所以只能用线段树套平衡树上了..上一次写这玩意还是用pascal的时候..

【#10】CRB and Roads 压位大法好，顺便学了一下bitset感觉好学好用好写..

【#10】CRB and String 两次看错题WA了若干发..其实只要判一下开头的一段相同前缀的长度以及第一个串是不是第二个串的子序列就好了。

【#10】CRB and Substrings 以前和DZY讨论过这个问题..但是只会[tex]\log^2[/tex]的做法..所以比赛的时候看到这道题就懵逼了..这题可以用构造后缀树的Ukkonen算法的一个拓展来直接做到[tex]O(nq)[/tex]，北棒子的题解写了和没写一样..CC上gerald出过一道类似的题，那儿的题解还是非常详细的。

【#10】CRB and Tree 比赛的时候做的，一条路径的权值等于它两个端点到根节点的路径的权值异或起来，所以直接用trie树上就好了。