洛谷3128
思路
要进行多次的树上某一段路径的加法操作，暴力做法时间复杂度较大，考虑差分。
对树上路径的两个端点进行操作，在进行遍历的时候将路径的其他点的值还原，从而降低时间复杂度。
注意思路来自董晓算法
代码实现
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
vector<int>v[100005];
int n,k;
int fa[100005][21];
int w[100005]={0};
int dev[100005]={0};
void dfs(int u,int father)
{
dev[u]=dev[father]+1;
fa[u][0]=father;
for(int i=1;i<=20;i++)
{
//if(fa[u][i-1]!=0)
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i:v[u])
{
if(i==father)
continue;
dfs(i,u);
}
}
int lca(int x,int y)
{
if(dev[x]<dev[y])
swap(x,y);
for(int i=20;i>=0;i--)
{
if(dev[fa[x][i]]>=dev[y])
x=fa[x][i];
}
if(x==y)
return y;
for(int i=20;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int ans=0;
int solve(int u,int fat)
{
for(int i:v[u])
{
if(i==fat)
continue;
solve(i,u);
w[u]+=w[i];
}
return w[u];
}
signed main()
{
cin.tie(NULL);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n-1;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
//cout<<lca(4,5)<<" j jj"<<'\n';
for(int i=1;i<=k;i++)
{
int s,t;
cin>>s>>t;
int l=lca(s,t);
w[s]++;
w[t]++;
w[l]--;
w[fa[l][0]]--;
}
solve(1,0);
for(int i=1;i<=n;i++)
ans=max(w[i],ans);
cout<<ans;
return 0;
}