[NOIP2016]天天爱跑步
#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
int re(){
int x=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int n,m,cnt;
int last[N],w[N],t[1000],dep[N],val[N],t1[N],t2[N];
vector<int>v1[N],v2[N];
struct edge{int to,next;}e[N<<1];
void link(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void solve1(){
while(m--){t[re()]++;re();}
for(int i=1;i<=n;i++){
if(!w[i])printf("%d ",t[i]);
else printf("0 ");
}
}
void solve2(){
while(m--){t[re()]++;re();}
for(int i=1;i<=n;i++)printf("%d ",t[i]);
}
bool dfs(int u,int ed,int time,int fa){
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa)continue;
if(dfs(v,ed,time+1,u)){
t[u]+=(w[u]==time);
return 1;
}
}
if(u==ed)t[u]+=(w[u]==time);
return u==ed;
}
void solve3(){
while(m--){
int st=re(),ed=re();
dfs(st,ed,0,0);
}
for(int i=1;i<=n;i++)printf("%d ",t[i]);
}
void solve4(){
while(m--){
int st=re(),ed=re();
if(st<=ed)t1[st]++,v1[ed].push_back(st);
else t2[st]++,v2[ed].push_back(st);
}
for(int i=1;i<=n;i++){
if(i>w[i])val[i]+=t1[i-w[i]];
int sz=v1[i].size();
for(int j=0;j<sz;j++)t1[v1[i][j]]--;
}
for(int i=n;i>=1;i--){
if(i+w[i]<=n)val[i]+=t2[i+w[i]];
int sz=v2[i].size();
for(int j=0;j<sz;j++)t2[v2[i][j]]--;
}
for(int i=1;i<=n;i++)printf("%d ",val[i]);
}
void dfs(int u,int fa){
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa)continue;
dep[v]=dep[u]+1;
dfs(v,u);val[u]+=val[v];
}
}
void solve5(){
while(m--){re();val[re()]++;}
dfs(1,0);
for(int i=1;i<=n;i++)
printf("%d ",w[i]==dep[i]?val[i]:0);
}
void dfs1(int u,int fa){
t2[dep[u]]+=t1[u];int pre=t2[dep[u]+w[u]];
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
}
val[u]=t2[dep[u]+w[u]]-pre;
}
void solve6(){
while(m--){t1[re()]++;re();}
dfs(1,0);dfs1(1,0);
for(int i=1;i<=n;i++)printf("%d ",val[i]);
}
int main(){
n=re(),m=re();int Type=n%10;
for(int i=1,u,v;i<n;i++){
u=re(),v=re();link(u,v);
}
for(int i=1;i<=n;i++)w[i]=re();
if(Type==1)solve1();
if(Type==2)solve2();
if(Type==3)solve3();
if(Type==4)solve4();
if(Type==5)solve5();
if(Type==6)solve6();
return 0;
}
部分分拼了6档,80分
考noip就要像这样,难题一般有很多部分分,一档一档想,不要贪AC
关键点就在一个链的部分分和一个(T_i=1)的部分分
-
链
一个点的答案只有两个来源,(i-w_i)和(i+w_i)
但是从这两个点出发不一定走得到(i),也不一定往(i)走
考虑分成向上走和向下走,先预处理出每个点向上走和向下走的人数
现在的问题就在于走不走得到了,在每个人的终点处打个标记,用vector存
考虑从前往后带个桶走,走到一个终点就把它对应的起点取出来,这样走不到的在之前就已经被取出了 -
(Ti=1)
答案就是这个点的子树中有多少满足(dep[v]=dep[u]+w[u])
一个套路:
还是开桶,进这个点的时候记录一下桶的元素个数,扫完子树再查一下,作差即可 -
(S_i=1)是什么?差分
把上面三个拼起来,就有了正解的思路
首先,一个人被观察到那么这个人一定经过了观测点,即这条路径经过观测点才有可能产生答案,
于是这条路径的S或T一定在观测点的子树中,分开求S和T的贡献(这样就只需要考虑子树)
把一条路径拆开,(S->lca)和(lca->T)
还是带个桶走,
走到(S,T),把的贡献加进来,走到(lca)取出来
- S的贡献:(dep[s]=dep[u]+w[u])
每个S贡献唯一,直接开桶记 - T的贡献:(dep[t]-dep[u]+w[u]=dep[s]+dep[t]-2dep[lca])
消掉dep[t],变成(w[u]-dep[u]=dep[s]-2dep[lca])
这样每个T有多种贡献,开vector记一下,
还因为有可能是负的,所以开map存
每个点的答案依然用(T_i=1)的套路求(ans[u]=t1[w[u]dep[u]]+t2[w[u]-dep[u]])
但(lca)处算了两遍贡献,特判(dep[st]==dep[lca]+w[lca])减掉1
#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
int re(){
int x=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int n,m,cnt,lca;
int w[N],last[N],t[N],dep[N],top[N],son[N],fa[N],sz[N],ans[N],met[N];
struct edge{int to,next;}e[N<<1];
vector<int>v1[N],v2[N],f[N];
map<int,int>vis;
void link(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs(int u){
sz[u]=1;
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa[u])continue;
dep[v]=dep[u]+1;
fa[v]=u;dfs(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs(int u,int tp){
top[u]=tp;
if(son[u])dfs(son[u],tp);
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v!=fa[u]&&v!=son[u])dfs(v,v);
}
}
void Query(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
lca=dep[u]<dep[v]?u:v;
}
void dfs1(int u){
int s=v1[u].size(),pre=met[w[u]+dep[u]];
met[dep[u]]+=t[u];
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v!=fa[u])dfs1(v);
}
ans[u]+=met[w[u]+dep[u]]-pre;
for(int i=0;i<s;i++)met[dep[v1[u][i]]]--;
}
void dfs2(int u){
int s=v2[u].size(),pre=vis[w[u]-dep[u]];
int sx=f[u].size();
for(int i=0;i<sx;i++)vis[f[u][i]]++;
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(v!=fa[u])dfs2(v);
}
ans[u]+=vis[w[u]-dep[u]]-pre;
for(int i=0;i<s;i++)vis[v2[u][i]]--;
}
int main(){
n=re(),m=re();
for(int i=1,u,v;i<n;i++){
u=re(),v=re();link(u,v);
}
dfs(1);dfs(1,1);
for(int i=1;i<=n;i++)w[i]=re();
while(m--){
int st=re(),ed=re();
t[st]++;Query(st,ed);
f[ed].push_back(dep[st]-2*dep[lca]);
if(dep[st]==dep[lca]+w[lca])ans[lca]--;
v1[lca].push_back(st);
v2[lca].push_back(dep[st]-2*dep[lca]);
}
dfs1(1);dfs2(1);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}