T1 Description
给出一个长度为N的数列{a[n]}，1<=a[i]<=M(1<=i<=N)。
现在问题是，对于1到M的每个整数d，有多少个不同的数列b[1], b[2], …, b[N]，满足：
(1)1<=b[i]<=M(1<=i<=N)；
(2)gcd(b[1], b[2], …, b[N])=d；
(3)恰好有K个位置i使得a[i]<>bi
注：gcd(x1,x2,…,xn)为x1, x2, …, xn的最大公约数。
输出答案对1,000,000,007取模的值。
Input
第一行包含3个整数，N，M，K。
第二行包含N个整数：a[1], a[2], …, a[N]。
Output
输出M个整数到一行，第i个整数为当d=i时满足条件的不同数列{b[n]}的数目mod 1,000,000,007的值。
Sample Input
输入1：
3 3 3
3 3 3
输入2：
3 5 3
1 2 3
Sample Output
输出1：
7 1 0
当d=1，{b[n]}可以为：(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1)。
当d=2，{b[n]}可以为：(2, 2, 2)。
当d=3，因为{b[n]}必须要有k个数与{a[n]}不同，所以{b[n]}不能为(3, 3, 3)，满足条件的一个都没有。
输出2：
59 3 0 1 1
T2 Description
某一天，少年邂逅了同病相连的IA。见面后，IA一把牵起少年的手，决定和他一起逃离部落，离开这个无法容身的是非之地。
要逃离部落，少年和IA就需要先选择一条耗时最少的路线，从而避免被部落的大人们抓到。部落可以大致分为N个区域，少年和IA在区域1，部落的出口设在区域N。此外部落还有M条连接两个区域道路。道路是无向的，没有一条道路的两端连接相同的区域，也没有两条道路所连接的两个区域完全相同。对于其中前(M−1)条道路，其通过时间是确定的，但最后一条道路，由于地理因素，通过其的时间会不断变化。
现在，少年和IA得知了在K个不同的时段里，通过第M条道路的时间，请您分别计算出在这K 个时段中逃离部落的最少时间，以帮助他们确定行动的时刻。
Input
第一行三个整数N,M,K，分别表示区域数，道路数，询问数。
接下来M−1行每行三个整数ui,vi,wi(ui≠vi,1≤ui,vi≤N,0
Output
输出共计K行，每行一个整数，表示对应时段逃离部落的最短时间。如果在该时段内无法逃离，输出“+Inf”。
Sample Input
输入1：
4 5 4
1 2 7
1 3 4
2 4 3
3 4 6
2 3
1
2
4
6
输入2：
4 3 1
1 2 7
1 3 4
2 3
9
Sample Output
输出1：
8
9
10
10
输出2：
+Inf
Data constraint
n<=200000,m<=500000,k<=30000
T3 Description
H国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。绝对不会出现这样的关系：A是B的上级，B也是A的上级。
最开始的时刻是0，你要做的就是用1单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。
现在，你想知道：
1.到底需要多长时间，消息才能传遍整个H国的所有人？
2.要使消息在传递过程中消耗的时间最短，可供选择的人有那些？
Input
输入文件的第一行为一个整数N（N≤20000），表示H国人的总数，假如人按照1到n编上了号码，国王的编号是1。
第2行到第N行（共N-1行），每一行一个整数，第i行的整数表示编号为i的人直接上级的编号。
Output
输出共计两行：
第一行为一个整数，表示最后一个人接到消息的最早时间。
第二行有若干个数，表示可供选择人的编号，按照编号从小到大的顺序输出，中间用一个空格隔开。
Sample Input
输入1：
4
1
1
1
输入2：
8
1
1
3
4
4
4
3
Sample Output
输出1：
4
1 2 3 4
输出2：
5
3 4 5 6 7
Data Constraint
对于20%的数据，满足N<=3000；
对于50%的数据，满足N<=20000；
对于100%的数据，满足N<=200000；
比赛总结
考试的时候不太专注，总是想东想西的。而且做题策略有问题，一上来就想先切掉第三题，确实也想到了很多东西，但是有一个关键的操作不会做，就GG了。
于是没有时间去做第二题~没想到第二题是最简单的，我觉得如果我好好想是可以做出来的，结果只是草草看了一遍题面，连暴力都没时间打，然而暴力分有60+
Solution
T1
运用组合数学，考虑正难则反。
每次枚举一个公约数i，统计出a数列有多少个是i的倍数，即为sum 则可以推出公式。
记得，这样算出来的是公约数为i，而不是最大公约数为i，所以要筛一下。
T2
先不把最后一条边加进去。然后以1为源点跑一次spfa，存入dis数组，再以n为源点跑一次spfa，存入dist数组。
记最后一条边的两端是x和y，长度为z，则新的最短路为min(dis[n],dist[x]+dis[y]+z,dis[x]+z+dist[y]);
T3
子树之间不能互相影响。
每次合并子树的时候，肯定是先排序，然后最大的子树最先走。
由此可以得出20分算法。
先以1为根，每次旋根，根旋转之后只会改变一部分子树，按照bfs的顺序，新根的后面的所有子树的贡献都会减一，然后逐个改就可以了。
改题总结
第一次打spfa的SLF优化，果然快的飞起，省去了打堆优化的dij的麻烦。
对组合数学的运用还很不熟练，需要刷一点这方面的题目。
下周要段考了，段考之后全身心投入训练中吧。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=300050;
const int mo=1000000007;
int n,m,k,i,j;
ll w[maxn],w1[maxn],ans[maxn],a[maxn],p[maxn];
int read(){
int sum=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') {
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
ll mi(ll x,ll y){
if (y==0) return 1;
if (y==1) return x;
ll t;
t=mi(x,y>>1);
if (y&1==1) return t*t%mo*x%mo;
else return t*t%mo;
}
ll c(ll cnt,ll n,ll k){
return w[cnt]*w1[cnt-n+k]%mo*w1[n-k]%mo;
}
int main(){
n=read(),m=read(),k=read();
for (i=1;i<=n;i++) {a[i]=read(); p[a[i]]++;}
w[0]=1;
for (i=1;i<=n;i++) w[i]=w[i-1]*i%mo;
w1[n]=mi(w[n],mo-2);
w1[0]=1;
for (i=n-1;i>=1;i--) w1[i]=w1[i+1]*(i+1)%mo;
for (i=1;i<=m;i++){
ll cnt=0;
for (j=i;j<=m;j+=i) cnt+=p[j];
if (cnt<n-k) { ans[i]=0; continue;}
ans[i]=c(cnt,n,k)*mi(m/i-1,cnt-n+k)%mo*mi(m/i,n-cnt)%mo;
}
for (i=m;i>=1;i--)
for (j=i+i;j<=m;j+=i) ans[i]=(ans[i]-ans[j]+mo)%mo;
for (i=1;i<=m;i++) printf("%d ",ans[i]);
}#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const ll inf=1000000000000007;
const int maxn=200050;
ll dis[maxn],q[maxn],dist[maxn],next[maxn*5],head[maxn*5];
bool vis[maxn];
ll tot;
ll n,m,k,ans,x,y,z; int i;
struct edge{
int l,r;
} b[maxn*5];
int read(){
ll sum=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') {
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
void add(int x,int y,int z){ next[++tot]=head[x]; head[x]=tot; b[tot].l=y; b[tot].r=z;}
void spfa(){
int l,r,x,i;
dis[1]=0; l=0; r=1; q[1]=1;
vis[1]=true;
while (l<r) {
x=q[++l];
vis[x]=false;
for (i=head[x];i;i=next[i]) {
if (dis[b[i].l]>dis[x]+b[i].r) {
dis[b[i].l]=dis[x]+b[i].r;
if (!vis[b[i].l]) {
vis[b[i].l]=true;
q[++r]=b[i].l;
if (dis[b[i].l]<dis[q[l+1]]) swap(q[l+1],q[r]);
}
}
}
}
}
void faps(){
int l,r,x,i;
dist[n]=0; l=0; r=1; q[1]=n;
memset(vis,false,sizeof(vis));
vis[n]=true;
while (l<r) {
x=q[++l];
vis[x]=false;
for (i=head[x];i;i=next[i]) {
if (dist[b[i].l]>dist[x]+b[i].r) {
dist[b[i].l]=dist[x]+b[i].r;
if (!vis[b[i].l]) {
vis[b[i].l]=true;
q[++r]=b[i].l;
if (dist[b[i].l]<dist[q[l+1]]) swap(q[l+1],q[r]);
}
}
}
}
}
int main(){
freopen("monogatari.in","r",stdin);
freopen("monogatari.out","w",stdout);
for (i=1;i<=m-1;i++) {
x=read(),y=read(),z=read();
add(x,y,z); add(y,x,z);
}
for (i=1;i<=n;i++) dis[i]=inf;
for (i=1;i<=n;i++) dist[i]=inf;
spfa();
faps();
x=read(); y=read();
for (i=1;i<=k;i++){
z=read();
ans=inf;
ans=min(ans,dis[n]);
ans=min(dis[x]+z+dist[y],ans);
ans=min(dist[x]+z+dis[y],ans);
if (ans!=inf) printf("%lld\n",ans);
else printf("+Inf\n");
}
}#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=200050;
int n,i,rr,tot;
int fa[maxn],head[2*maxn],next[2*maxn],b[2*maxn],ans[maxn],q[maxn],c[maxn],f[maxn],g[maxn],sum[maxn];
int pre[maxn],aft[maxn];
int read(){
int sum=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') {
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
void add(int x,int y){next[++tot]=head[x];head[x]=tot;b[tot]=y;}
bool cmp(int x,int y){
return x>y;
}
bool cmpp(int x,int y){
return sum[x]>sum[y];
}
void bfs(){
int l,r,i,j,x,cnt;
l=0; r=1; q[1]=1;
while (l<r){
x=q[++l];
for (i=head[x];i;i=next[i])
if (b[i]!=fa[x]) q[++r]=b[i];
}
for (j=n;j>=1;j--){
cnt=0; x=q[j];
for (i=head[x];i;i=next[i]) if (b[i]!=fa[x]) c[++cnt]=f[b[i]];
sort(c+1,c+cnt+1,cmp);
for (i=1;i<=cnt;i++) f[x]=max(f[x],c[i]+i);
}
ans[1]=f[1];
rr=min(rr,ans[1]);
for (j=1;j<=n;j++){
cnt=0; x=q[j];
for (i=head[x];i;i=next[i]) if (b[i]!=fa[x]) c[++cnt]=b[i],sum[b[i]]=f[b[i]];
if (j!=1) c[++cnt]=fa[x],sum[fa[x]]=g[x];
sort(c+1,c+cnt+1,cmpp);
for (i=1;i<=cnt;i++) ans[x]=max(ans[x],sum[c[i]]+i);
rr=min(rr,ans[x]);
pre[0]=aft[cnt+1]=0;
for (i=1;i<=cnt;i++) pre[i]=max(pre[i-1],sum[c[i]]+i);
for (i=cnt;i>=1;i--) aft[i]=max(aft[i+1],sum[c[i]]+i-1);
for (i=1;i<=cnt;i++) if (c[i]!=fa[x]) g[c[i]]=max(pre[i-1],aft[i+1]);
}
}
int main(){
freopen("news.in","r",stdin);
freopen("news.out","w",stdout);
n=read();
for (i=2;i<=n;i++) {
fa[i]=read();
add(fa[i],i),add(i,fa[i]);
}
rr=1000000000;
bfs();
printf("%d\n",rr+1);
for (i=1;i<=n;i++)
if (ans[i]==rr) printf("%d ",i);
}