D. AB Graph 2000 构造
https://codeforces.com/problemset/problem/1481/D
题解：由于只有两种边，我们可以枚举较小结构的特性并循环来构造整体解。对于任意两个点，[u->v,v->u]只有4种情况，对于[1,1],[0,0]直接得解，可以循环这个环来构造回文，否则[1,0],[0,1]，注意到当所需回文为odd长时，此时可循环abababab得到解。接下来讨论长度为even时且不存在某两点间存在[1,1]或[0,0]边的情况：此时若n/2为odd，我们可以构造形如aabbaabbaabb能够保证从中切割后是回文，当n/2是even时，我们可以构造abbaabbaabba满足条件。此时两个点所有的条件无法构造出合适的解，我们考虑任意3个点u,v,w。若v->u为1，v->w为1,结合先前条件，我们可以给出abbaabba和aabbaabb的路径。而由抽屉原理，这样的v在n>=3时总是存在的（若有某2个点出边均为同色且均为a或b,则存在2元环，当n>=3时由抽屉原理必存在）。故得到构造。
E. Two Chess Pieces 1900 思维，树
https://codeforces.com/problemset/problem/1774/E
题解：最短操作数为两棋子所需经过的所有点的路径长度和。首先题给出的点是必要经过的，注意到距离<=d即等价于a中每个点的d祖先需要b经过，对b同理，这样添加完所有必要经过点后，我们只要分别计算a,b的必要经过路径之和即可得到答案，因为我们可以将所有必经点放入一个集合中按dfs序排序，当下一个必经点属于a，就然a前去该点，当即将超出距离限制时，我们让另一点前往其下一个必经点，由于前述条件，下一必经点必然是满足距离限制的，故成立。
代码实现也有技巧，比如找d祖先时我们可以维护一个数组存d[i]=x时的点，此时a[d[x]-D]即为D祖先。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=5e5+10;
int ans[3],v[N],vis[3][N],a[N],b[N],w[N],f[N],d,dis[N],e[N];
vector<int> g[N];
void dfs(int x,int fa){
f[x]=fa;
e[dis[x]]=x;
if(dis[x]>=d) w[x]=e[dis[x]-d];
for(auto it:g[x]){
if(it==fa) continue;
dis[it]=dis[x]+1;
dfs(it,x);
}
}
void up(int k,int x){
if(vis[k][x]) return;
if(x==0) return;
vis[k][x]=1;
up(k,f[x]);
}
void dfss(int k,int x,int fa){
ans[k]++;
for(auto it:g[x]){
if(it==fa||vis[k][it]==0) continue;
dfss(k,it,x);
ans[k]++;
}
}
bool cmp(int x,int y){
return dis[x]>dis[y];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;cin>>n>>d;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
g[x].pb(y),g[y].pb(x);
}
dfs(1,0);
int m1,m2;
cin>>m1;
for(int i=1;i<=m1;i++){
cin>>a[i];
}
cin>>m2;
for(int i=1;i<=m2;i++) cin>>b[i];
for(int i=1;i<=m1;i++){
if(w[a[i]]!=0)
b[++m2]=w[a[i]];
}
for(int i=1;i<=m2;i++){
if(w[b[i]]!=0)
a[++m1]=w[b[i]];
}
sort(a+1,a+m1+1,cmp);
sort(b+1,b+m2+1,cmp);
for(int i=1;i<=m1;i++){
if(vis[1][a[i]]) continue;
up(1,a[i]);
}
for(int i=1;i<=m2;i++){
if(vis[2][b[i]]) continue;
up(2,b[i]);
}
dfss(1,1,0);
dfss(2,1,0);
cout<<ans[1]+ans[2]-2<<endl;
}
D. Lost Arithmetic Progression 1900 组合计数 数论
https://codeforces.com/problemset/problem/1673/D
题解：特判0解和无穷解的情况。
对于有解的情况，我们发现lcm(da,db)=dc,而答案即为dc/dadc/da,换句话说我们只需找到所有da即可，而da必为dc的因子，故我们可以sqrt(dc)找到所有因子后若因子满足dadb/gcd(da,db)==dc，则加入答案，复杂度为sqrt(N)log(N)。
#include<bits/stdc++.h>
#define int long long
#define forn(i,n) for(int i=1;i<=n;i++)
#define pb push_back
using namespace std;
const int N=2e5+100,mod=1e9+7;
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
void solve(){
int b1,q1,c1,b2,q2,c2;
cin>>b1>>q1>>c1>>b2>>q2>>c2;
if(q1>q2||q2%q1||b2<b1||((b1+q1*(c1-1))<(b2+q2*(c2-1)))||(b2-b1)%(q1)){
cout<<0<<endl;return;
}
if(b2-b1<q2||(b1+q1*(c1-1))-(b2+q2*(c2-1))<q2){
cout<<-1<<endl;return;
}
int ans=0;
for(int i=1;i*i<=q2;i++){
if(q2%i!=0) continue;
if(i*q1/gcd(i,q1)==q2)
ans=(ans+(q2/i)*(q2/i)%mod)%mod;
int w=q2/i;
if(i*i==q2) continue;
if(w*q1/gcd(w,q1)==q2)
ans=(ans+(q2/w)*(q2/w)%mod)%mod;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
}