Problem
- 有一颗 nn个节点的树,k 次旅行,问每一条边被走过的次数。
Solution
- 优化到最后才发现是个树上差分。。。
- 树上差分:对于一条树链,u和v+1,lca的父亲(本题里面是lca)-2。
- 本题相当于离线,如果修改和访问交替就需要树链剖分了。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1e5+5;
int n,k,cnt,last[maxn],dep[maxn],logg[maxn*4],f[maxn][30],ft[maxn];
int num[maxn],ans[maxn],ac[maxn];
vector<int>ceng[maxn];
struct edge{
int v,next;
}e[maxn<<1];
void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=last[u];
last[u]=cnt;
}
void dfs1(int x,int fa)
{
for(int i=1;i<=20;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=last[x];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dep[v]=dep[x]+1;
ceng[dep[v]].push_back(v);
f[v][0]=x;
ft[v]=x;
num[v]=i/2+i%2;
dfs1(v,x);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]!=dep[v])
u=f[u][logg[dep[u]-dep[v]]];
if(u==v)
return u;
for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i])
{
u=f[u][i];
v=f[v][i];
}
return f[u][0];
}
int main()
{
for(int i=1;i<=100005;i++)
logg[i]=logg[i-1]+((1<<(logg[i-1]+1))==i);
cin>>n;
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
cin>>k;
dfs1(1,0);
for(int i=1,u,v;i<=k;i++)
{
scanf("%d%d",&u,&v);
ac[u]++;
ac[v]++;
ac[lca(u,v)]-=2;
}
for(int i=100000;i>=0;i--)
{
for(int j=0;j<ceng[i].size();j++)
{
int u=ceng[i][j];
ans[num[u]]+=ac[u];
ac[ft[u]]+=ac[u];
}
}
cout<<ans[1];
for(int i=2;i<n;i++)
cout<<' '<<ans[i];
}