Fools and Roads CodeForces - 191C
题意：给出一棵n个节点的树，还有树上的k条简单路径（用路径的两个端点u和v表示），对于树上每一条边，求出其被多少条简单路径经过。
方法：
一开始想了很久..想要在倍增求lca的同时统计边经过的次数..然而发现这样子可以统计，但是统计的值拆不开...没有办法在合适时间内得到答案...并没有思路..
想了很久发现，这其实就是个简单的树上差分，只要记录一下每个节点i到根节点路径上所有边都需要加的权值sum[i]就行了。
对于每一组(u,v)，题意操作转化为sum[u]++,sum[v]++,sum[lca(u,v)]-=2。
最后用一遍dfs把sum拆开，这个"树上前缀和"是可以O(n)拆开的。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
vector<LL> v[];
vector<P> vv;
LL T,n,ne,k;
LL deep[],anc[][],log2n,sum[],ans[];
void dfs(LL x,LL fa)
{
LL i;
anc[x][]=fa;
deep[x]=deep[fa]+;
for(i=;i<=log2n;i++)
anc[x][i]=anc[anc[x][i-]][i-];
for(auto y:v[x])
if(y!=fa)
dfs(y,x);
}
LL lca(LL x,LL y)
{
LL t,i;
if(deep[x]<deep[y]) swap(x,y);
for(t=deep[x]-deep[y],i=;t>;t>>=,i++)
if(t&) x=anc[x][i];
if(x==y) return x;
for(i=log2n;i>=;i--)
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
return anc[x][];
}
void dfs2(LL x,LL fa)
{
for(auto y:v[x])
if(y!=fa)
dfs2(y,x);
ans[x]+=sum[x];sum[fa]+=sum[x];
}
int main()
{
LL i,x,y;
scanf("%lld",&n);log2n=log2(n);
for(i=;i<n;i++)
{
scanf("%lld%lld",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
vv.push_back(P(x,y));
}
dfs(,);
scanf("%lld",&k);
for(i=;i<=k;i++)
{
scanf("%lld%lld",&x,&y);
sum[x]++;sum[y]++;sum[lca(x,y)]-=;
}
dfs2(,);
for(auto k:vv) printf("%lld ",ans[deep[k.first]>deep[k.second]?k.first:k.second]);
return ;
}