D. GCD Counting
题意：
给出n个点的树，每个点有一个权值，找出一条最长的路径使得路径上所有的点的gcd>1
题解：
gcd>1的一定不会有很多。所以暴力搞一下就行，不需要点分治。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map> using namespace std;
const int maxn=2e5+;
int head[maxn],Next[*maxn],to[*maxn];
int a[maxn];
int n,sz;
void init(){
sz=;
memset(head,-,sizeof(head));
}
void add_edge(int a,int b){
++sz;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
}
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
map<int,int>mp[maxn];
int ans;
void dfs(int u,int fa){
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(v==fa)continue;
dfs(v,u);
map<int,int>::iterator it,it2;
for(it=mp[v].begin();it!=mp[v].end();it++){
int g=gcd((*it).first,a[u]);
if(g<=)continue;
for(it2=mp[u].begin();it2!=mp[u].end();it2++){
int g2=gcd((*it2).first,g);
if(g2<=)continue;
ans=max(ans,(*it).second+(*it2).second+);
}
mp[u][(*it).first]=max(mp[u][(*it).first],(*it).second);
}
}
// printf("%d %d\n",u,ans);
mp[u].clear();
mp[u][a[u]]=;
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(v==fa)continue;
map<int,int>::iterator it;
for(it=mp[v].begin();it!=mp[v].end();it++){
int g=gcd(a[u],(*it).first);
if(g<=)continue;
mp[u][g]=max(mp[u][g],(*it).second+);
ans=max(ans,(*it).second+);
}
}
} int main(){
scanf("%d",&n);
init();
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>)ans=;
} for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(,);
printf("%d\n",ans);
return ;
}
F. Trucks and Cities
题意：
一条笔直公路上有n个城市，第i个城市在a[i]的位置。有m辆卡车要从一个城市去另一个城市，每一辆卡车有四个属性来描述：s,f,c,r.分别是开始的城市，结束的城市，油耗，可以加油的数量。当卡车到达一个城市的时候就可以加油，每次加油都加满，开始的时候所有的车油都是满的。请你找到最小的V使得所有的卡车都能到达目的地。
题解：
对于一辆从s到t的车，它有k次加油的机会。发现实际上是将s到t的路径以城市为端点最多划分为最大长度最小的k+1段。可以发现这样是最优的。然后就dp+单调队列优化。
代码留坑···
G. (Zero XOR Subset)-less
题意：
给出n个整数a1,a2,...,an。你的任务是将这n个整数分成最多段用下面的方法 1.每个元素都被一段包含 2.每一段都包含至少一个元素 3.每一个非空的段的子集，他们的xor不等于0.
输出最多能分成几段，如果没有合法的分段方法，输出-1.
题解：
当这n个数xor起来如果为0那么肯定是无解的。然后求线性基，线性基的大小r就是答案····
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream> using namespace std;
typedef long long LL;
const int maxn=2e5+;
LL a[maxn];
LL x[];
int n;
int main(){
scanf("%d",&n);
LL sum=;
for(int i=;i<=n;i++){
scanf("%I64d",&a[i]);
sum^=a[i];
}
if(sum==){
printf("-1\n");
return ;
}
int r=;
for(int i=;i<=n;i++){
for(int j=;j>=;j--){
if(!(a[i]>>j))continue;
if(!x[j]){
x[j]=a[i];
r++;
break;
}
a[i]^=x[j];
}
}
printf("%d\n",r);
return ;
}