因为是第一次写题解就按着模板来了qwq
题目描述
在树上跑路径,求每个点经过多少次。
样例
5
1 4 5 3 2
1 2
2 4
2 3
4 5
画一个图可以很好的理解ovo
法一、树链剖分
不会,咕~
法二、LCA
看到之后,我立马想到了标记,遇到两个点跑一次,跑一次标记一次,但仔细想想会挂掉www(没写,口糊,你可以试试ovo)
然后我就康到了隔壁题解里的:树上差分(类比差分数组)。
假设跑的点为x,y,num[x,y]+1,作为一个树会上传来修改(所以最后跑一遍dfs可以统计答案),但是上传之后会发现lca(x,y)更新了两次,所以num[lca(x,y)]-1,为了不影响其他数,fa[lca(x,y)][0]-1。
不懂的话可以画图,再不懂的话: 树上差分
细节很多
C++ 代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=3e5+5;
int n,a[N],t;
int cnt,head[N];
struct Edge{
int from,to,nxt;
}e[N<<1];
inline void add(int u,int v){
e[++cnt]=(Edge){u,v,head[u]};
head[u]=cnt;
}
int f[N][21],d[N];
queue<int>q;
void bfs(int s){
q.push(s);d[s]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(d[y])continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=t;j++)
f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
}
int lca(int x,int y){
if(d[x]>d[y])swap(x,y);
for(int i=t;i>=0;i--){
if(d[f[y][i]]>=d[x])y=f[y][i];
}
if(x==y)return x;
for(int i=t;i>=0;i--){
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int num[N];
void sol(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
sol(y,u);
num[u]+=num[y];
}
}//统计树上差分答案
int main(){
n=read();
t=(int)log(n)/log(2)+1;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1,x,y;i<n;i++){
x=read(),y=read();
add(x,y);
add(y,x);
}
bfs(1);
for(int i=1;i<n;i++){
int u=a[i],v=a[i+1];
int t=lca(u,v);
num[f[t][0]]-=1;
num[t]-=1;
num[u]+=1;num[v]+=1;
}
sol(1,0);
for(int i=2;i<=n;i++){
num[a[i]]--;
}//因为查询a1 a2 a3 a4时询问a1&a2 ,a2&a3,a3&a4所以多加了一次,这里减去
for(int i=1;i<=n;i++)printf("%d\n",num[i]);
return 0;
}
%%%