前言：
一场 没有大样例 别开生面的模拟赛......
\(T1：\)染色(color)
题意：
给一个长度为\(n\)的序列染色，使得对于任意的\(1≤i<j≤n\)，若\(|i-j|\)为质数，则\(i\)与\(j\)不同色。求出颜色尽可能少的染色方案。
思路：
一道规律题。众所周知，在质数内，只有\(2\)为偶数，其余质数都为奇数。所以我们可以考虑奇偶染色，即\(12121212...\)，但是又因为有\(2\),所以我们将\(4\)作为一个循环节的长度，即\(123412341234...\)。但是显然，当\(n\)小于\(8\)时，我们根本凑不齐\(2\)整个循环节，没有必要填\(4\)种颜色，这样是不优的。因此我们可以填\(11223344\)（至于为什么是这个序列？自己手模一下就知道了。）
代码：
$凤凰栖于梧桐树$
#include<iostream>
using namespace std;
const int N=1e4+5;
int n,col[N];
int main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);ios::sync_with_stdio(false);cin>>n;if(n>6){cout<<4<<'\n';for(int i=1,cnt=1;i<=n;i++,cnt++){cout<<cnt<<" ";cnt%=4;//4位一循环 }return 0;}//n大于6 cout<<((n+1)>>1)<<'\n';//小于6 if(n%2==0) for(int i=1,cnt=1;i<=n;i+=2,++cnt) cout<<cnt<<" "<<cnt<<" ";else for(int i=1,cnt=1;i<=n;i+=2,cnt++){if(i==n) cout<<cnt;else cout<<cnt<<" "<<cnt<<" ";}return 0;
}
\(T2：\)序列(array)
没xiáo会，等我xiáo会了再说
\(T3：\)树上询问(query)
题意：
给定一棵\(n\)个节点的树\(T\)，每次询问给两个整数\(l\),\(r\)，问存在多少个整数\(k\)使得从\(l\)沿着\(l→r\) 的简单路径走\(k\)步恰好到达\(k\)。
思路：
一般人肯定都会想到把路径拆分为两条链，\(l→lca(l,r)\)和\(lca(l,r)→r\)。然后我们一步一步往上跳，遇到满足条件的点就把答案加一。一点都不难嘛，写个\(dfs\)把图固定根节点变成成树，再求\(lca\)，最后在线跑一边路径就好了。\(But......\)你会发现你光荣的\(TLE\)了，所以要考虑优化，怎么优化？不难发现，在\(l→lca(l,r)\)上符合条件的点为\(dep[l]-dep[x]=x\)，可以化为\(dep[x]+x=dep[l]\)，在\(lca(l,r)→r\)上符合条件的点为\(dep[l]-dep[lca]+dep[x]-dep[lca]=x\)，可化简为\(dep[x]-x=2*dep[lca]-dep[l]\)。然后我们发现等号右边的我们可以预处理，因此我们将询问离线下来，然后使用树上前缀和差分预处理右边的式子，最后再跑一遍\(dfs\)统计答案就好啦~~
代码：
$沐光而行衔美玉$
#include<iostream>
#include<vector>
using namespace std;
const int N=3e6+5;
int m,n,u,v,cnt,l[N],r[N],head[N],dep[N],fa[N],f[N],vis[N],dis[2][N<<1],lca[N],ans[N];
struct node{int to,nxt;}e[N];
struct wutong{int v,id;};
struct jade{int val,ch,dif,id;};
vector<wutong> q1[N];vector<jade> q2[N];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}//建边
inline int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}//找祖宗
inline void dfs1(int bb,int daddy){dep[bb]=dep[daddy]+1;f[bb]=daddy;for(int i=head[bb];i;i=e[i].nxt){int y=e[i].to;if(y!=daddy) dfs1(y,bb);}
}//固定树
inline void dfs2(int bb,int daddy){vis[bb]=1;for(int i=head[bb];i;i=e[i].nxt){int y=e[i].to;if(y!=daddy){dfs2(y,bb);fa[y]=bb;}}for(auto y:q1[bb]) if(vis[y.v]) lca[y.id]=find(y.v);
}//预处理lca
inline void dfs3(int bb,int daddy){dis[0][dep[bb]+bb]++;//前半段 dis[1][dep[bb]-bb+n]++;//后半段 for(auto y:q2[bb]) ans[y.id]+=y.dif*dis[y.ch][y.val];//差分统计答案 for(int i=head[bb];i;i=e[i].nxt){int y=e[i].to;if(y==daddy) continue;dfs3(y,bb);}dis[0][dep[bb]+bb]--;dis[1][dep[bb]-bb+n]--;
}
int main(){
// freopen("query.in","r",stdin);
// freopen("query.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i;//初始化 for(int i=1;i<n;i++){cin>>u>>v;add(u,v);add(v,u);//建边 }for(int i=1;i<=m;i++){cin>>l[i]>>r[i];q1[l[i]].push_back({r[i],i});q1[r[i]].push_back({l[i],i});//把询问离线下来 }dfs1(1,0);dfs2(1,0);//预处理 for(int i=1;i<=m;i++){q2[l[i]].push_back({dep[l[i]],0,1,i});q2[lca[i]].push_back({dep[l[i]],0,-1,i});//前半段 q2[r[i]].push_back({2*dep[lca[i]]-dep[l[i]]+n,1,1,i});if(lca[i]>1) q2[f[lca[i]]].push_back({2*dep[lca[i]]-dep[l[i]]+n,1,-1,i});//后半段 }dfs3(1,0);for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';//输出答案 return 0;
}//关于dfs中的变量名纯为恶趣味 如果不懂且想懂的话建议去问港城的朋友~~