题解
本人的虚树入门题。
基础思想
题目意思相当于m次询问，每次询问给出一些点，要我们付出一定代价断边使得给出的这些点与根节点1不连通.
首先肯定能确定这个题是一个树形DP。转移方程也非常好写。
考虑对于单次询问，我们设f[x]为处理完以x为子树的最小的代价。
那么转移无非是两种情况：
1.断开与父亲的连接，代价为从x到根1的路径上的最小值。
2.当该点不是询问点的时候，把子树内所有询问点都与根节点断开的代价。
但是这样有一个问题，每次询问都是O(n)的，来看一下数据范围：
很明显O(nm)的做法是无法处理的。
进阶优化 & 虚树的引出
但实际上，我们在对每一次询问的处理中，考虑了很多无用点的信息。
考虑一下，很容易能够明白，实际上，只有询问点、其LCA、其LCA的LCA及其三次LCA……等，对这些点和上面的根进行断开是实际在最小答案中有效的，处理其他的点实际上无效。
所以虚树就应运而生了。
虚树是主要运用在树形DP中的一类构造方法，旨在只将对答案有用的点拿出来构造一棵虚拟的新的树，以此来降低算法的复杂度。
举个栗子，在本题的样例中有这样的数据。
对于样例中的询问数据
3 2 10 6 4 5 7 8 3 3 9 4 6
其对应的虚树分别是以下的形式
第二个询问中，由于点7、8均在5的子树内，故断开5以及根节点的连接即可，7、8实际上是无用点（仅对此题而言，不同题目要考虑不同的构造）
虚树的构建
现在需要考虑的是如何构建虚树。
首先我们要先对整棵树dfs一遍，求出他们的dfs序，然后对每个节点以dfs序为关键字从小到大排序(本人比较喜欢用树链剖分里面的那种形式)
同时维护一个栈，表示从根到栈顶元素这条链
假设当前要加入的节点为pp，栈顶元素为x=s[top]x=s[top]，lcalca为他们的最近公共祖先
因为我们是按照dfs序遍历，因此lcalca不可能是pp
那么现在会有两种情况
- lcalca是xx，直接将
题目大意
玩家Little Sub和lqybzx分别有N、M个数对(xi,yi)、(x'i,y'i),且双方都知道对方的数对中的数是什么，Little Sub先从自己的N个数对中的每个数对中选取1个数z，并且ans = ans xor z,之后lqybzx会对自己的M个数对做相同的操作。
Little Sub(A)希望最终结果更大，而lqybzx(B)希望最终结果更小，且双方均采取最优策略，问最终答案是多少。
题解
对于博弈的题目来说，我们其实不是好知道双方的脑回路是怎么想的。有时候我们能猜到有时候我们猜不到。
所以不妨我们先来假设两个人每个数对都选第一个数字，先把一个答案ans算出来，然后我们来根据每个人的数对再来进行调整。
由于是二进制的运算所以我们考虑对每个答案ans的每个二进制位上是否为1来讨论两个玩家的策略。
因为我们需要对二进制位进行讨论，所以我们需要讨论两个玩家的数对(x,y)中x xor y对答案的控制能力。所以我们需要对两个玩家的数对(x,y)进行x xor y的线性基的构造。
假设构造的两个x xor y的线性基分别为A、B。
如果在某个位bit上我们取了线性基X中在bit位上的元素，我们相当于在总答案的上面对某一组数对(x,y)的选择进行改变(ans xor(x xor y),本来ans中有x或y，选择这一次相当于换成另外一个)
我们从高位到低位逐一进行扫描，对于第i位，分为以下八种情况：
ans[i] = 0,A[i] = 0,B[i] = 0,双方都对这个位无法操作
ans[i] = 0,A[i] = 0,B[i] = 1,只有B对这个位可以操作，但由于B想要答案更小，所以他不会对这一位进行操作。
ans[i] = 0,A[i] = 1,B[i] = 0,只有A对这个位可以操作，由于A想要答案更大，所以他会选择对这一位进行操作，ans ^= A[i]。
ans[i] = 0,A[i] = 1,B[i] = 1,A与B都可对这个位操作，而且如果A对这个位操作的话，B一定也会对这个位操作，所以我们可以把A[i] xor B[i]加入到线性基A中，表示A和B同时选/不选。
ans[i] = 1,A[i] = 0,B[i] = 0,双方都对这个位无法操作
ans[i] = 1,A[i] = 0,B[i] = 1,只有B对这个位可以操作，由于B想要答案更小，所以他会选择对这一位进行
题目大意
给出一棵n个节点的树，要求将这个树的所有节点映射到一张1000000*20的横向表格里，要求保持原先的连边映射成的相连线段不能有交叉。
输出一种方案，要求将所有的树上节点的坐标输出。
题解
行数最多只有20行，所以要考虑最大行数控制在log2n以内。所以就要想树上的什么东西一定小于小于等于log2n。
学过树链剖分的话不难想到，对一个树进行重链剖分的话，所有点向下的轻链长度一定小于等于log2n，树链剖分的复杂度就是基于这个性质证明的。这个性质的证明并不难想，因为对于一个节点x，其轻儿子的子树大小一定不会超过siz[x]/2，否则这个儿子就是重儿子了。
然后就可以明白，要先对树进行重链剖分，对每个节点now把重儿子和自己放在同一行上，轻儿子放在下一行，重儿子和自己的距离间隔为siz[now]-siz[son[now]]，第一个轻儿子v1放在(x[now],y[now]+1)，第二个轻儿子v2放在(x[now]+siz[v1],y[now]+1),第三个轻儿子v3放在(x[now]+siz[v1]+siz[v2],y+1)，以此类推。
因为横向的列数极多，所以横向不会出现问题，又由轻链长度的性质，纵向不会不会超过20.上述的放节点的留空就是为了使得边不会交叉采取的方案。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
vector<int>g[maxn];
int son[maxn],siz[maxn],f[maxn];
struct point{
int x,y;
}p[maxn];
void dfs(int now,int fa){
siz[now] = 1;
son[now] = 0;
f[now] = fa;
for(auto it : g[now]){
if(it == fa)continue;
dfs(it,now);
siz[now] += siz[it];
if(siz[it] > siz[son[now]])
son[now] = it;
}
return;
}
void work(int now,int
题目大意
给出n个k维向量vi，对于k维空间中所有点a，将点a与点a+vi连边，求问全部连接完的图能否完成黑白染色。
题解
黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。
考虑二分图形成的条件：不能出现奇环。
于是问题就转变成了如何判断图中是否会存在奇环。
但是这个题目明显不能用通常的搜索判环解决。
考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。
假设n个未知数xi，假设一个点想要回到自身，需要使用第i个向量xi次。
于是要形成环即向量方程：
x1v1 + x2v2 + ... + xnvn = 0有解。
所以如果要保证形成奇数环的话，就是加入以下一个方程
x1 xor x2 xor ... xor xn = 1
联立来解一个n元k+1维方程组。
将上面的向量方程拆分到k维k个方程，并将所有运算全都mod 2处理，即可让整个方程组变成一个异或方程组。
能形成二分图的条件就是方程组不存在解，否则就说明构成的图不是二分图。
使用高斯消元解决方程组判断解的问题。
但是高斯消元有一个问题，就是复杂度不对，为O(nk2)
不过由于这道题的方程组的运算只与二进制异或有关，所以可以把方程的参数放入bitset加速，最终复杂度为O(nk2/64)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= k;++j){
cin >> x;
g[j][i] = abs(x) % 2;
}
}
for(int i = 1;i <= n+1;++i){
g[k+1][i] = 1;
}
now = 0;
for(int i = 1;i <= n;++i){
int j
Example
15 1 2 3 1 2 3 3 1 1 3 2 2 1 2 3 1 2 1 3 1 4 1 14 1 15 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
题目大意
给出一棵有根树，树上每个点有一个颜色，求问以每一个节点x为根的子树内数量最多的颜色的编号的和sum为多少。
题解
如果暴力统计的话，时间复杂度将会成为O(n2)，这是我们没办法接受的。
貌似可以搞什么线段树合并还有莫队什么的。
但是复杂度好像依旧还是太高，于是就有这么一个神奇的东西叫dsu on tree，中文名叫树上启发式合并。
dsu实际上是并查集的问题，但这个算法并不是什么树上并查集，而是借鉴了并查集中启发式合并优化的思想，将这个思想运用到了树上。
结合树链剖分的性质，将所有的树链分为轻链和重链后，对于每一个子树的根节点rt：轻链子节点sq，递归进入计算以sq为根的子树的答案，但是不保存，递归结束时清空；重链子节点son，递归进入计算以son为根的子树的答案，递归结束时不清空，作为rt为根节点的子树的基础答案。
之后对于以rt为根节点的子树，在重链子节点son的子树提供的基础答案上，再暴力计算该子树其它所有轻链子树和rt节点本身的答案，与刚刚的基础答案合并，可以解算出以rt为根节点的子树的答案。
通过树链剖分的轻重链性质，不难证明答案的复杂度应该为O(nlog2n)，因为所有节点被访问的次数至多为log2n次。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int x,y;
typedef long long ll;
ll ans[maxn],c[maxn],sum,mx;
int son[maxn],siz[maxn],f[maxn],cnt[maxn];
vector<int>g[maxn];
int n,s;
void dfs(int now,int fa){
f[now] = fa;
siz[now] = 1;
for(auto it : g[now]){
if(it == fa)continue;
dfs(it,now);
siz[now
题目大意
给出一张个点的完全图，两点和 ()的路径的距离被定义为：
设 表示i到j的最短距离，求
题解
题目挺绕的，可能会让人误以为是图论题。但是一看数据范围就不是。所以就来考虑最短路的性质。
显然的，假设节点的编号分别被进行了质因子分解，表达成唯一分解定理的表达式，那么两点的最短距离，如果在两节点编号各质因子的幂次的奇偶性均相同时为1，否则一定为：
其中均没有为因子，且奇偶性不同。
很简单，如果两点有多个因子不同，那么我们完全可以途经其它节点来走，让质因子相加取代相乘，这样一定是最小的。
于是就可以直接分最短路径为1和不为1两种情况来讨论。
首先讨论为1的情况，这种情况下我们把两数指数为奇数的乘在一起，假设为，这样就是两个介于
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
typedef long long ll;
ll g[maxn],w[maxn],id1[maxn],id2[maxn],spr[maxn],smu[maxn],pr[maxn];
int nop[maxn],mu[maxn];
const ll mod = 998244353;
int tot = 0,cnt = 0;
void euler_init(){
nop[1] = 1;
mu[1] = 1;
smu[1] = 1;
for(int i = 2;i < maxn;++i){
if(!nop[i]){
mu[i] = -1;
pr[++tot] = i;
spr[tot] = spr[tot-1] + i;
}
smu[i] = smu[i-1] + (mu[i] == 0 ? 0 : 1);
for(int j = 1;j <= tot && pr[j] * i < maxn;++j){
nop[pr[j] * i] = 1;
if(i % pr[j] == 0){
mu[i*pr[j]] = 0;
break;
}
mu[i*pr[j]] = -mu[i];
}
}
return;
}
ll A(ll n,ll p){
if(p*p > n)return n / p;
return n/p - A(n/p,p);
}
ll S(ll n){
if(n < maxn)return smu[n];
ll ans = 0;
for(ll d = 1;d*d <= n;++d){
if(mu[d] == 1)
ans = (ans + n / d / d % mod) % mod;
题目大意
有s种动物排成一个长度为n的队伍，有l种朋友关系a b，动物a和动物b为朋友可以互相交换位置，但是当且仅当这两种动物在相邻位置时。
问在所有的可能交换位置的方案后，序列最小的字典序排列是什么。
题解
挺难想的一个题，看题解只有一句话，看代码看了好久才想明白。
通过动物之间的朋友关系，我们可以确定可以互相交换的有哪些位置，也可以确定哪些动物的相对位置是不能发生改变的。
于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点，来进行拓扑排序（当然是字典序更小的动物为更优先序的）
首先给所有物种的名字排序保证是字典序，然后用二维数组E：0 表示两个物种可以交换（是朋友），1表示不能交换（不是朋友）、二维数组Fij：0表示物种i的当前最前位置的一个在物种j当前最前位置的前面，1则相反。
然后枚举每个位置放哪个物种，如果当前物种i满足有一个j使得Eij & Fij = 1，那么就说明这个物种当前最前面的个体之前有不能与其交换的个体，就不能在当前这个位置放这个物种的这个个体，就需要放其它物种。如果满足没有这样的j，那么这个位置就放物种i了（这时字典序一定最小），然后更新一下Fij（因为是Fij表示的是两物种当前未被放入序列种的最靠前的个题之间的位置关系），继续枚举下一位置放什么就可以了。
E和F由于只需要&操作，所以可以用bitset来进行加速。
代码
#include <bits/stdc++.h>
using namespace std;
int s,l,n;
const int maxn = 205;
vector<int>pos[maxn];
string a,b;
vector<string>name;
int id(string str){
return lower_bound(name.begin(),name.end(),str) - name.begin();
}
bitset<maxn>e[maxn],f[maxn];
vector<int>ans;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> l >> n;
name.reserve(s);
for(int i = 0;i < s;++i){
cin >> a;
题目大意
给定起点和终点以及一些中继点的坐标，距离如题目描述中所示，有0-T这些道路，每种道路上每公里排放CO2数量不同，为ci L / km。
你的车最多能跑B（B≤100）公里，每个中继点连接着另外一些中继点，且连通的道路种类有规定。起点和终点到其它中继点的道路全为种类0.
问能不能从起点到达终点，如果不能输出-1，否则输出最少排放的CO2数。
题解
首先不管别的，先把道路建起来，所有中继点的关系已经给出，而起点和终点需要额外建立两个点，并且设定连向所有的点。
本来看起来是像是个最短路，但是因为有规定最大的里程数，所以普通的最短路算法并不能适用。
但是注意到最大里程数B较小，所以我们可以考虑到某个点在跑了x公里的情况下最小的排放CO2的量是多少，然后通过类似于最短路的BFS对这个维护量进行转移。
即，假设dp[i][j]表示跑到节点i，且已经跑了j公里，所排放的最小CO2的量。
剩下的就是通过类似spfa的bfs进行转移，注意判断边界即可。
代码
#include <bits/stdc++.h>
using namespace std;
int xs,ys,xt,yt;
const int maxn = 1005;
int T,B,n;
const int INF = 1e9+7;
const int maxe = 1e6+5;
int dp[maxn][105];
int c[105];
struct point{
int x,y;
}p[maxn];
typedef pair<int,int>PI;
vector<PI>g[maxn];
int dis(int a,int b){
double x = sqrt(double((p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)));
return (int)ceil(x);
}
struct node{
int id,dis,cos,pre;
};
struct edge{
int to,next,dis,cos;
}e[maxe<<1];
int h[maxn];
int cnt = 0;
void add(int u,int v,int d,int c){
e[cnt].to
题目大意
定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。
现在给定一个树，树上每个节点有权值，树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。
求问这种路径权值的最大值是多少。
题解
此题解为搬运CodeForces官方题解，为其中文翻译版本。（严正声明，可能中间会加一些个人的理解，代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了）
首先确认这是一个树上路径问题，针对树上路径问题，一般可用的方法就是树分治和树链剖分。
考虑到这道题的路径权值的定义，我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算，我们大概需要用搜索算法才能确定一个路径的权值和长度。
但是问题是，路径总数实在太多了，我们是不可能把所有路径都找出来算一遍的。所以我们考虑采用点分治，看看如何去减少对路径的统计。
考虑使用树分治，这里使用点分治更为方便（当然我也不会边分治），因为下面的思路是依靠点分治经过树的重心的路径这一思路展开的。
我们考虑一个树，经过重心的一个路径u->rt->v，我们分成u->rt和rt前往v的路径的下面一个点x->v两条路径来看。
假设路径u->rt的路径权值为为presum、路径上所有点的值的和为precnt，路径x->v的路径的路径权值为precalc、长度为prelen。
那么u->v的路径的路径权值为：
sum = precnt*prelen + presum + precalc
这是一个一次函数的形式，可以看作是一个直线在某点处的取值问题。
具体而言可以看作一条斜率为prelen，参数为precalc的直线在x = precnt处的取值（最后再加上一个presum）
那么对于前半部分路径对后半部分路径进行组合结果计算的问题就转化成了求后半部分的路径代表的多个直线在某点处的取值的最大值问题（最高点）。
但是用什么来计算呢？暴力肯定行不通的。
这里介绍李超线段树。李超线段树的用途是，维护区间内最高的线段。其思想是线段树的每个节点保存在当前区间中心点mid处最高的线段。每当加入一条线段时，先检测当前区间中心点mid处这条线段的高度与原来的线段相比，然后更低的线段向其左/右孩子更新。李超线段树可以查询在某点处最高的高度为多少。具体实现可以看代码。
于是我们通过点分治和李超线段树可以成功地把此题的复杂度降低到O(nlog2n)，并且成功计算出