【图论】【LCA】NOIP2016 天天爱跑步

分析：

诶。。再次觉得两年前的自己是个智障。。这题虽然号称全场最难。。但其实$O(nlogn)$算法还是挺好想的（而且可以使用tarjan算法优化lca，使得复杂度优化为$O(n)$）

无非就是LCA随便搞搞。。。对于每个跑步的人，把它拆分为2个，一个从u出发，只往上跑，时间递增，跑到$lca(u,v)$为止。一个从v出发，只往上跑，时间递减（出发时间为dist(u,v)），也跑到$lca(u,v)$为止。

然后对于一个观察员，如果它能观察到一个时间递增的人，那么：
$w_i=deep_{pos_j}-deep_i+st_j$（j表示一个跑步者，$st_j$表示它的起始时间，$deep_{pos_j}$表示j的起始位置。$pos_j$在i的子树中）
移一下项，变成
$w_i+deep_i=st_j+deep_{pos_j}$。
所以可以存储：每个时间递增跑步者的起始位置的时间+它起始位置的深度。

如果它能观察到一个时间递减的人，那么：
$w_i=deep_i-deep_{pos_j}+st_j$
再移一下项，变为：
$w_i-deep_i=st_j-deep_{pos_j}$
所以可以存储：每个时间递减跑步者的起始位置的时间-它起始位置的深度。

然后特殊处理一下刚好在lca位置的观察员。。。就可以过了。。。
这是$O(nlogn)$的算法，考场上加了一堆优化防卡常，效率还算不错

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 300010
using namespace std;
void Read(int &x){x=0;char c;while(c=getchar(),c!=EOF&&(c<'0'||c>'9'));x=c-'0';while(c=getchar(),c!=EOF&&c>='0'&&c<='9')x=x*10+c-'0';   
}
struct node{int x;node *nxt;  
}edge[MAXN*2];
node * head[MAXN],* ncnt=edge;
vector<int> add1[MAXN],add2[MAXN],del1[MAXN],del2[MAXN];
int w[MAXN],ans[MAXN];
int n,m;
void add_edge(int x,int y){ncnt++;ncnt->x=y;ncnt->nxt=head[x];head[x]=ncnt;
}
int dep[MAXN],fa[MAXN][20];
void dfs(int x,int f){fa[x][0]=f;for(int i=1;i<19&&fa[x][i-1];i++)fa[x][i]=fa[fa[x][i-1]][i-1];dep[x]=dep[f]+1;for(node *v=head[x];v!=NULL;v=v->nxt){int u=v->x;if(u==f)continue;dfs(u,x);   }
}
int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);for(int i=18;i>=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];if(u==v)return u;for(int i=18;i>=0;i--)if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}return fa[u][0];
}
int cnt1[MAXN*2],cnt2[MAXN*2];
void solve(int x,int f){int val1=cnt1[w[x]+dep[x]];int val2=cnt2[w[x]-dep[x]+n];for(node *v=head[x];v!=NULL;v=v->nxt){int u=v->x;if(u==f)continue;solve(u,x); }for(int i=0;i<add1[x].size();i++)cnt1[add1[x][i]]++;for(int i=0;i<add2[x].size();i++)cnt2[add2[x][i]]++;for(int i=0;i<del1[x].size();i++)cnt1[del1[x][i]]--;for(int i=0;i<del2[x].size();i++)cnt2[del2[x][i]]--;int valx1=cnt1[w[x]+dep[x]];int valx2=cnt2[w[x]-dep[x]+n];ans[x]+=valx1-val1+valx2-val2;
}
int main(){Read(n),Read(m);int u,v,val;for(int i=1;i<n;i++){Read(u),Read(v);add_edge(u,v);add_edge(v,u);}for(int i=1;i<=n;i++)Read(w[i]);dfs(1,0);for(int i=1;i<=m;i++){Read(u),Read(v);int l=lca(u,v);int len=dep[u]+dep[v]-2*dep[l];add1[u].push_back(dep[u]);add2[v].push_back(len-dep[v]+n);del1[l].push_back(dep[u]);del2[l].push_back(len-dep[v]+n);if(w[l]==dep[u]-dep[l])ans[l]++;}solve(1,0);for(int i=1;i<=n;i++)PF("%d ",ans[i]);
}

这是$O(n)$的代码
可能写得有点丑，导致实际运行时差距并不大

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 300010
using namespace std;
void Read(int &x){x=0;char c;while(c=getchar(),c!=EOF&&(c<'0'||c>'9'));x=c-'0';while(c=getchar(),c!=EOF&&c>='0'&&c<='9')x=x*10+c-'0';   
}
struct node{int x;node *nxt;  
}edge[MAXN*2];
struct rns{int u,v,lca;
}p[MAXN];
node * head[MAXN],* ncnt=edge;
vector<int> add1[MAXN],add2[MAXN],del1[MAXN],del2[MAXN];
vector<pair<int,int> > que[MAXN];
int w[MAXN],ans[MAXN];
int n,m;
void add_edge(int x,int y){ncnt++;ncnt->x=y;ncnt->nxt=head[x];head[x]=ncnt;
}
int dep[MAXN],fa[MAXN];
int cnt1[MAXN*2],cnt2[MAXN*2];
void solve(int x,int f){int val1=cnt1[w[x]+dep[x]];int val2=cnt2[w[x]-dep[x]+n];for(node *v=head[x];v!=NULL;v=v->nxt){int u=v->x;if(u==f)continue;solve(u,x); }for(int i=0;i<add1[x].size();i++)cnt1[add1[x][i]]++;for(int i=0;i<add2[x].size();i++)cnt2[add2[x][i]]++;for(int i=0;i<del1[x].size();i++)cnt1[del1[x][i]]--;for(int i=0;i<del2[x].size();i++)cnt2[del2[x][i]]--;int valx1=cnt1[w[x]+dep[x]];int valx2=cnt2[w[x]-dep[x]+n];ans[x]+=valx1-val1+valx2-val2;
}
bool vis[MAXN];
int get_fa(int x){if(fa[x]==0)return x;fa[x]=get_fa(fa[x]);return fa[x];
}
void dfs(int x,int f){vis[x]=1;for(int i=0;i<que[x].size();i++){int u=que[x][i].first;int id=que[x][i].second;if(vis[u]==1)p[id].lca=get_fa(u);}for(node *v=head[x];v!=NULL;v=v->nxt){int u=v->x;if(u==f)continue;dep[u]=dep[x]+1;dfs(u,x);fa[u]=x;}
}
int main(){Read(n),Read(m);int u,v,val;for(int i=1;i<n;i++){Read(u),Read(v);add_edge(u,v);add_edge(v,u);}for(int i=1;i<=n;i++)Read(w[i]);for(int i=1;i<=m;i++){Read(p[i].u),Read(p[i].v);que[p[i].u].push_back(make_pair(p[i].v,i));que[p[i].v].push_back(make_pair(p[i].u,i));}dfs(1,0);for(int i=1;i<=m;i++){u=p[i].u;v=p[i].v;int l=p[i].lca;int len=dep[u]+dep[v]-2*dep[l];add1[u].push_back(dep[u]);add2[v].push_back(len-dep[v]+n);del1[l].push_back(dep[u]);del2[l].push_back(len-dep[v]+n);if(w[l]==dep[u]-dep[l])ans[l]++;}solve(1,0);for(int i=1;i<=n;i++){PF("%d",ans[i]);if(i!=n)PF(" ");}
}