树上差分半裸题
常规思路是进行三次DFS，然后常规运算即可
这里提供两次dfs的思路（wyz tql orz）
我们以样例2为例
我们考虑任意一条路径，令其起点为u终点为v，每走一次当前路径则v的访问次数必定+1，于是我们可以使每一个点表示连接其上的一条边的访问次数，所以我们令节点v的访问次数+1;
与此同时，过程中的路径也同样会被访问，且这里是双向边，于是与此同时的我们也令节点u的访问次数+1;当然访问当前子树下根节点中包含的两个点并不会访问，而我们在增加u和v的访问时同时也错误地增加了其公共父节点的访问量，于是我们令lca(u,v)的访问量-2即可。
例如上图中我们从节点5走到节点3，我们令节点3与节点5的访问次数+1，同时使节点4的访问次数-2。
如下：
while(k--){
int u=read(),v=read();
diff[u]++,diff[v]++,diff[lca(u,v)]-=2;
}
最后输出答案时只需要判断每条边两端点的深度大小即可。
#include<bits/stdc++.h>
#define int long long
#define maxn 100005
using namespace std;
inline char get(){
static char buf[30000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
struct edge{
int u,v,w,next;
int num=0;
}E[maxn<<1];
int n,k;
int p[maxn],eid;
int d[maxn], parent[maxn][20];
int diff[maxn];
inline void init(){
for(register int i=0;i<maxn;i++)p[i]=d[i]=-1;
eid=0;
}
inline void insert(int u,int v){
E[eid].u=u;
E[eid].v=v;
E[eid].next=p[u];
p[u]=eid++;
}
inline void insert2(int u,int v){
insert(u,v);
insert(v,u);
}
void dfs(int u){
for (register int i=p[u];~i;i=E[i].next) {
if (d[E[i].v]==-1){
d[E[i].v]=d[u]+1;
parent[E[i].v][0]=u;
dfs(E[i].v);
}
}
}
int lca(int x, int y) {
int i,j;
if(d[x]<d[y])swap(x,y);
for(i=0;(1<<i)<=d[x];i++);
i--;
for(register int j=i;j>=0;j--){
if (d[x]-(1<<j)>=d[y])x=parent[x][j];
}
if(x==y)return x;
for(register int j=i;j>=0;j--){
if(parent[x][j]!=parent[y][j]) {
x=parent[x][j];
y=parent[y][j];
}
}
return parent[x][0];
}
int dd[maxn];
void dfs_(int u,int fa,int flag){
dd[u]=flag;
for(register int i=p[u];~i;i=E[i].next){
int v=E[i].v;
if(fa==v)continue;
dfs_(v,u,flag+1);
diff[u]+=diff[v];
}
}
int u[maxn],v[maxn];
signed main(){
//freopen("1.txt","r",stdin);
init();
n=read();
for(register int i=2;i<=n;i++){
u[i]=read(),v[i]=read();
insert2(u[i],v[i]);
}
d[1]=0;
dfs(1);
for(register int level=1;(1<<level)<=n;level++){
for(register int i=1;i<=n;i++){
parent[i][level]=parent[parent[i][level-1]][level-1];
}
}
k=read();
while(k--){
int casu=read(),casv=read();
diff[casu]++,diff[casv]++,diff[lca(casu,casv)]-=2;
}
dfs_(1,-1,1);
for(register int i=2;i<=n;i++){
if(dd[u[i]]>=dd[v[i]])cout<<diff[u[i]]<<" ";
else cout<<diff[v[i]]<<" ";
}
return 0;
}