倍增法求LCA
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
typedef long long ll;
int a[N];
int h[N], e[2*N], ne[2*N], idx;
int fa[N][25];//f[i][j]表示i节点的2^j个父节点
int d[N];//当前点的深度
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int f)
{
d[u]=d[f]+1;
fa[u][0]=f;//记录当前点的父节点
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
dfs(j,u);
}
}
int lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
while(d[x]>d[y]) x=fa[x][(int)log2(d[x]-d[y])];
//找到当前点能走到的最小的比d[y]要大的点,然后继续从这个点开始走直到走到d[y]一层的点上
if(x==y) return y;//要是x走到了y上面,那么直接返回y不用继续跳了
for(int j=20;j>=0;j--)//从大往小走
{
if(fa[x][j]!=fa[y][j])
x=fa[x][j],y=fa[y][j];
//要是两个点的2^j节点还是不一样那就都跳
//要是一样了那就不急着跳,因为跳了可能不是最小的公共祖先
//直到走到最接近lca的点,然后这个点的父节点就是lca
}
return fa[x][0];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q,root;
cin>>n>>q>>root;
memset(h, -1, sizeof h);
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(root,0);
for(int j=1;j<=20;j++)//直接从2^1开始,2^0已经记录过
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];//当前点的2^j等于当前点走2^(j-1)的点再走2^(j-1)
while(q--)
{
int a,b;
cin>>a>>b;
cout<<lca(a,b)<<endl;
}
}
树上差分
按点差分
$$ mark[x]\++,mark[y]\++,mark[lca(x,y)]\–,mark[fa(lca(x,y))]\– $$
当前点修改的值为当前点子树mark值之和
按边差分
将边权变成子节点的点权,根节点则没有点权
$$ mark[x]\++,mark[y]\++,mark[lca(x,y)]\-=2 $$
当前点修改的值为当前点子树mark值之和
按层差分
从上往下dfs
深搜节点——打标记——算答案——回溯
codeforces——1076E
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
#define int long long
typedef pair<int, int> pii;
int h[N],e[2*N],ne[2*N],idx;
int n,m;
int d[N];
int ans[N],mark[N];//mark数组存的是当前点的差分数组
int sum;
vector<pii>ve[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
for(int i=0;i<ve[u].size();i++)
{
mark[d[u]]+=ve[u][i].second;
if(d[u]+ve[u][i].first+1<=n) mark[d[u]+ve[u][i].first+1]-=ve[u][i].second;
}
sum+=mark[d[u]],ans[u]=sum;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
}
sum-=mark[d[u]];
for(int i=0;i<ve[u].size();i++)
{
mark[d[u]]-=ve[u][i].second;
if(d[u]+ve[u][i].first+1<=n) mark[d[u]+ve[u][i].first+1]+=ve[u][i].second;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
memset(h, -1, sizeof h);
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
cin>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
ve[a].push_back({b,c});
}
dfs(1,0);
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}