。。蒟蒻被老师撵去写题解，无奈。没什么功夫去写两天的t1了，这里先放D1T2和D2T3吧
D1T2 天天爱跑步解题报告
感言：这道题当时在考场上修修补补，一点一点挤牙膏地得到了正解，可是竟然最后被下标坑了，蒟蒻就是借口多:-(
一种暴力算法O(n^2)
- 考虑到最朴素的思想，对每个人一步一步的跑到起点终点的lca，并统计到当前点x的时间Ti，对答案统计
即
预处理lca（nlogn的倍增算法）
每个跑步者单独处理，不断累计Ti，即if(Ti==W[a])ans[a]++;
for(int i=1;i<=n;i++)printf(“%d\n”,ans[i]); - 一共m位跑步者，每人最多跑n步，那么这个算法的时间复杂度是O(nm)的，期望得分25
一种树链剖分O(nlogn)，此处指向whj大神的blog
- 时间复杂度O(mlogn)，期望得分100（在洛谷上实测95 tle一个点，倍增的锅）
那么这已经是一种AC算法了，难道下面就没有了吗？
怎么可能？：）
第三种方法：O(n)
约定第i个人起终点的lca(s[i],t[i])为lca[i]，点i深度为dep[i]
- 考虑可能对点u有贡献的第i个跑步者，lca[i]肯定在u或者u上方，否则不经过u点，即lca[i]==u||lca[i]∉subtree[u]
-
基于此前提，只有两种情况（有重合部分）：①s[i]∈subtree[u] ②t[i]∈subtree[u]
分类讨论能被u看见的点v的情况
① v为i人起点s[i] dep[s[i]]-w[u]==dep[u]
② v为i人终点t[i] dep[s[i]]+dep[t[i]]-2*dep[lca[i]]-(dep[t[i]]-dep[u])==w[u]，即dep[s[i]]-2*dep[lca[i]]==w[u]-dep[u]
我们发现如果做个变换，即dep[u]+w[u]==dep[s[i]]
与 w[u]-dep[u]==dep[s[i]]-2*dep[lca[i]]的话，式子右边是不变的！于是我们考虑用一个桶cnt[2]来记录满足条件的点的数量即可
- 考虑使用cnt[2][600600]存储起点/终点的dep[s[i]]/dep[s[i]]-2*dep[lca[i]]等于j的点的数量
- 保存在数组cnt[0 or 1][j]中，那么当dfs中当前点到u的时候，ans[u]就可以从cnt数组中得到，特殊情况是：u为第i人的lca时可能导致s[i]与t[i]各对ans[u]贡献一次，所以式子如下
- ans[u]=cnt[0][dep[u]+w[u]]+cnt[0][w[u]-dep[u]]-（重复部分容易处理）;//两下标为上面两个等式的左式，需要注意的是dep[s[i]]-2*dep[lca[i]]有可能是负数，下标可以统一+300000处理成正数（本人栽在这里了）
- 维护cnt数组的方式容易想到就是在s[i],t[i],lca[i]上打标记，若当前点为s[i]就计入cnt[0][dep[s[i]]]，t[i]同理，lca[i]就把两个标记再退出去
- 然而如果对于每颗子树建立一个cnt，再把cnt合并的话，复杂度是n^2的。于是发现搜到以v为根的子树时后，对v贡献的只有两个下标，那么在搜索点v前，传两个参数a,b记录一下原来的cnt两个值，dfs(v,a,b)时ans[v]-=a+b即可
以下洛谷ac代码，20点共1232ms,极限数据n=m=300000用时312ms
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
#define N 600060
inline void rd(ll& x){
static char ch; while(!isdigit(ch=getchar()));
for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
}
inline void rd(int &x){
static ll T_T;
rd(T_T);x=T_T;
}
struct E{int v,nxt;};
typedef E zu[N];
typedef int arr[N];
arr s,t,fa,pos,fst,qf,ans,lc,w,dep,bj[2],bl[2],Cnt[2];
int n,m,tot,u,v,*cnt[2]={Cnt[0]+(N>>1),Cnt[1]+(N>>1)};
zu le,q,lian[2],L[2];
bool vis[N>>1];
inline int getf(int x){return (x==fa[x]?x:fa[x]=getf(fa[x]));}
inline void gl(int f,int &s,zu z){z[++tot]=(E){f,s},s=tot;}
inline int lca(int u,int d){
vis[u]=1;
dep[u]=d;
fa[u]=u;
for(int now=fst[u];now;now=le[now].nxt)
if(!vis[le[now].v])fa[lca(le[now].v,d+1)]=u;
for(int now=qf[u];now;now=q[now].nxt)
if(vis[q[now].v])lc[now>>1]=getf(q[now].v);
return u;
}
inline void make(int u,int a,int b){
vis[u]=0;
int v;
for(int now=fst[u];now;now=le[now].nxt)if(vis[v=le[now].v])
make(v,cnt[0][w[v]+dep[v]],cnt[1][w[v]-dep[v]]);
for(int now=qf[u];now;now=q[now].nxt)
cnt[!(now&1)][dep[s[now>>1]]-2*(!(now&1)?dep[lc[now>>1]]:0)]++;
ans[u]=cnt[0][w[u]+dep[u]]+cnt[1][w[u]-dep[u]]-a-b;
for(int now=bj[0][u];now;now=lian[0][now].nxt){
if(lian[0][now].v==w[u]+dep[u])ans[u]--;
cnt[0][lian[0][now].v]--;
}
for(int now=bj[1][u];now;now=lian[1][now].nxt)cnt[1][lian[1][now].v]--;
}
int main(){
rd(n),rd(m);
for(int i=1;i<n;i++){
rd(u),rd(v);
gl(v,fst[u],le);
gl(u,fst[v],le);
}
for(int i=1;i<=n;i++)rd(w[i]);
tot=1;
for(int i=1;i<=m;i++){
rd(s[i]),rd(t[i]);
gl(s[i],qf[t[i]],q);
gl(t[i],qf[s[i]],q);
}
lca(1,0);
tot=0;
for(int i=1;i<=m;i++){
gl(dep[s[i]],bj[0][lc[i]],lian[0]);
--tot,gl(dep[s[i]]-2*dep[lc[i]],bj[1][lc[i]],lian[1]);
}
make(1,0,0);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}D2T3 愤怒的小鸟解题报告
感言：原来以为都是两位小数，不会爆精度，值都够精确可以用==号，没想到被误差坑了，85分被卡剩20了大概，真的不应该，没话说
没什么好想，数据范围18，显然壮鸭低劈。预处理抛物线过哪几个点（随你n^2还是n^3），压进一个状态zt，若过k点就存进pw[k][++pw[k][0]]=zt里
需要注意的是，最终转移的时候如果枚举所有抛物线转移，共有n^2条抛物线，时间复杂度是t*n^2*2^n最后三个点会超时，然而很多抛物线事实上对当前状态没有贡献，所以只需要枚举 过编号最小的没有被杀的猪的n-1条抛物线即可，最终复杂度tn*2^n完美过（bfs式的状态转移不知道能不能ac，大家可以试试）
洛谷ac代码，时间共1274ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define exp 0.00000001
int t,n,m,tot,pw[20][20],num[400],er[20],dp[1000000];
long double x[20],y[20],a,b;
bool pd[1000000];
int main(){
scanf("%d",&t);
for(n=0,m=1;n<=19;m*=2)er[n++]=m;
while(t--){
memset(pd,0,sizeof(pd));
memset(dp,18,sizeof(dp));
memset(pw,0,sizeof(pw));
dp[0]=tot=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%Lf%Lf",&x[i],&y[i]);
for(int j=0;j<n;j++){
pw[j][++pw[j][0]]=er[j];
for(int i=0;i<n;i++)if(i^j){
if(x[i]==x[j])continue;
a=(y[i]-(x[i]*y[j])/x[j])/(x[i]*(x[i]-x[j]));
b=(y[i]-a*x[i]*x[i])/x[i];
if(a>=0||abs(a)<exp)continue;
int now=er[i]+er[j];
for(int k=0;k<n;k++)if(k!=i&&k!=j){
if(abs((a*x[k]+b)*x[k]-y[k])<exp)now+=er[k];
}
if(!pd[now])for(int k=0;k<n;k++)if(abs((a*x[k]+b)*x[k]-y[k])<exp)pw[k][++pw[k][0]]=now;
pd[now]=1;
}
}
for(int i=0;i<er[n]-1;i++){
tot=(i^(er[n]-1))&-(i^(er[n]-1));
for(int j=0;j<n;j++)if(er[j]==tot){tot=j;break;}
for(int j=1;j<=pw[tot][0];j++)dp[i|pw[tot][j]]=min(dp[i|pw[tot][j]],dp[i]+1);
}
printf("%d\n",dp[er[n]-1]);
}
}经验之谈（血泪教训Orz）
都是老生常谈了，只能说省选rp++，当积攒rp算了
- Day1 T2 考虑到下标有负数的情况，下标统一+300000，改的时候有一处没有改，那么就炸了，以后要注意可以用dev-cpp的“搜索”功能查找所有需要修改的地方
- Day1 T3 因为感觉会T2，我硬刚了T2甚至没看T3，后来才知道T3水题。这是OIer的大忌：不看完题
- Day2 T3 两位小数不会精度不足，也就是说足够精确，自信上了”==”号，后来发现”==”精度太高，计算误差就判不在抛物线上了，只剩20分。事实就是：没有什么小数题不用加eps。 PS：事后发现CCF数据跟洛谷比水得一匹，实际上有80分，只TLE了最后四个点。
- Day2 T2 一秒陷进了堆的思维，认栽。不过用堆的话：实测手写堆速度=stl priority_queue两倍，建议骗分的话多优化常数 PS：假的，pq跟手写堆都是60 ~QAQ
12.4更新
成绩11.28日出来了，签到题妥妥ac，出乎意料的是Day1 T2竟有55分，数据很仁慈，Day2 T3竟然该拿的80分全部拿到【看到成绩时笑疯，不过CCF的老爷机竟然卡了四个点，本来以为能95的】，不出意料的390果然还是个压线一等，毕竟Day1 T3水题没做。不说了，去做省选题喽