题面
传送门 题目大意: 给出一棵树,再给出k条树上的简单路径,求每条边被不同的路径覆盖了多少次
分析
解决这个问题的经典做法是树上差分算法 它的思想是把”区间”修改转化为左右端点的修改 在树上,每个节点初始权值为0,对于每条路径(x,y),我们令节点x的权值+1,节点y的权值-1,节点LCA(x,y)的权值-2 最后进行一次DFS,求出F[x]表示x为根的子树中各节点的权值之和,F[x]就是x与它的父节点之间的树边被覆盖的次数 用dfs序+ST表求LCA,时间复杂度
O(nlog2n+k)
O
(
n
l
o
g
2
n
+
k
)
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define maxn 100005
#define maxlog 32
using namespace std;
int n,k;
struct edge{
int from;
int to;
int next;
int index;
}E[maxn*
2];
int head[maxn];
int size=
0;
void add_edge(
int u,
int v,
int id){
size++;
E[size].from=u;
E[size].to=v;
E[size].next=head[u];
E[size].index=id;
head[u]=size;
}
int dfn[maxn*
2];
int used[maxn];
int fipos[maxn*
2];
int deep[maxn*
2];
int st[maxn*
4][maxlog];
int cnt=
0;
void get_dfn(
int u,
int d){
dfn[++cnt]=u;
if(fipos[u]==
0){
fipos[u]=cnt;
deep[u]=cnt;
}
used[u]=
1;
for(
int i=head[u];i;i=E[i].next){
if(!used[E[i].to]){
get_dfn(E[i].to,d+
1);
dfn[++cnt]=u;
}
}
}
void st_init(){
for(
int i=
1;i<=(n-
1)*
2;i++){
st[i][
0]=dfn[i];
}
for(
int j=
1;(
1<<j)<=(n-
1)*
2;j++){
for(
int i=
1;i<=(n-
1)*
2;i++){
if(deep[st[i][j-
1]]<deep[st[i+(
1<<(j-
1))][j-
1]]) st[i][j]=st[i][j-
1];
else st[i][j]=st[i+(
1<<(j-
1))][j-
1];
}
}
}
int st_query(
int l,
int r){
if(l>r) swap(l,r);
int k=log2(r-l+
1);
if(deep[st[l][k]]<deep[st[r-(
1<<k)+
1][k]])
return st[l][k];
else return st[r-(
1<<k)+
1][k];
}
int lca(
int x,
int y){
int fx=fipos[x];
int fy=fipos[y];
return st_query(fx,fy);
}
int len[maxn];
int outlen[maxn];
void get_len(
int u){
used[u]=
1;
for(
int i=head[u];i;i=E[i].next){
if(!used[E[i].to]){
get_len(E[i].to);
len[u]+=len[E[i].to];
outlen[E[i].index]+=len[E[i].to];
}
}
}
int main(){
int u,v;
scanf(
"%d",&n);
for(
int i=
1;i<=n-
1;i++){
scanf(
"%d %d",&u,&v);
add_edge(u,v,i);
add_edge(v,u,i);
}
get_dfn(
1,
0);
st_init();
scanf(
"%d",&k);
for(
int i=
1;i<=k;i++){
scanf(
"%d %d",&u,&v);
len[u]++;
len[v]++;
len[lca(u,v)]-=
2;
}
memset(used,
0,
sizeof(used));
get_len(
1);
for(
int i=
1;i<=n-
1;i++)
printf(
"%d ",outlen[i]);
}
