树上差分
概述：擅长在树上一条路径上统计边或者点的信息。
下文令差分数组为 \(d_i\)，\(lca\) 为路径两端点的 LCA，\(fa_i\) 为 \(i\) 的父亲。
-
按边的差分
将 \(a\) 到 \(b\) 的路径上的边权加 \(val\)：
-
按点的差分：
将 \(a\) 到 \(b\) 的路径上的点权加 \(val\)：
CF191C
一眼树剖。
容易发现这是一道绿题，因此不需要使用如此复杂的数据结构。
又因为这是统计边的信息，考虑树上差分。
其实这就是个板子，相当于每次旅行将 \(a \to b\) 路径上的边边权均 \(+1\)。直接按上文公式做即可。
注意因为差分数组是挂在点上的，所以需要维护一个边和点之间的映射。
code
//
// CF191C.cpp
//
//
// Created by _XOFqwq on 2024/10/11.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k;
int id[N],dp[N][31],diff[N],dep[N];
vector<pair<int,int> > G[N];
void init_lca(int cur,int fa){
dep[cur]=dep[fa]+1;
dp[cur][0]=fa;
for (int i=1; (1<<i)<=dep[cur]; i++) {
dp[cur][i]=dp[dp[cur][i-1]][i-1];
}
for (auto [nxt,i] : G[cur]) {
if (nxt==fa) {
continue;
}
id[i]=nxt;
init_lca(nxt,cur);
}
}
int get_lca(int x,int y){
if (dep[x]<dep[y]) {
swap(x,y);
}
for (int i=21; i>=0; i--) {
if (dep[dp[x][i]]>=dep[y]) {
x=dp[x][i];
}
}
if (x==y) {
return x;
}
for (int i=21; i>=0; i--) {
if (dp[x][i]!=dp[y][i]) {
x=dp[x][i],y=dp[y][i];
}
}
return dp[x][0];
}
void dfs(int cur,int fa){
for (auto [nxt,i] : G[cur]) {
if (nxt==fa) {
continue;
}
dfs(nxt,cur);
diff[cur]+=diff[nxt];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for (int i=1,u,v; i<n; i++) {
cin>>u>>v;
G[u].push_back({v,i});
G[v].push_back({u,i});
}
init_lca(1,0);
cin>>k;
for (int i=1,x,y; i<=k; i++) {
cin>>x>>y;
int lca=get_lca(x,y);
diff[x]++;
diff[y]++;
diff[lca]-=2;
}
dfs(1,0);
for (int i=1; i<n; i++) {
cout<<diff[id[i]]<<' ';
}
return 0;
}
P2680
还是很巧妙的一道题。
最短时间取决于 \(m\) 条路径的最大边权和，我们要最小化这个东西，直接考虑二分。
对于 \(m\) 条路径，只有边权和 \(> mid\) 的才有必要使用虫洞，设它们的数量为 \(tot\)。
我们要将这 \(tot\) 条路径的边权和全部变得 \(\le mid\)，因此只能选所有路径的公共边变成虫洞，并且还得选边权最大的。
找出公共边等价于找出被覆盖 \(tot\) 次的边，直接树上差分即可。
然后这题就做完了。需要适当卡常，详见代码。
code
//
// P2680.cpp
//
//
// Created by _XOFqwq on 2024/10/11.
//
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,tot,w[N];
int ddep[N],dep[N],dp[N][31],id[N],to[N],diff[N];
struct PATH{
int u,v,dis,lca;
}path[N];
struct EDGE{
int v,w,e;
};
vector<EDGE> G[N];
namespace fastIO{
#define BUF_SIZE 1000000
bool IOerror=0;
inline char nc() {
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1){
IOerror=1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
}
inline void read(int &x) {
char ch;
while(blank(ch=nc()));
if(IOerror) return;
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=(x<<3)+(x<<1)+ch-'0');
}
#undef BUF_SIZE
};
using namespace fastIO; //卡常 1
bool cmp(PATH x,PATH y){
return x.dis>y.dis;
}
void init_lca(int cur,int fa){
dep[cur]=dep[fa]+1;
dp[cur][0]=fa;
for (int i=1; (1<<i)<=dep[cur]; i++) {
dp[cur][i]=dp[dp[cur][i-1]][i-1];
}
for (auto [v,w,e] : G[cur]) {
if (v==fa) {
continue;
}
id[e]=v;
to[v]=e;
ddep[v]=ddep[cur]+w;
init_lca(v,cur);
}
}
int get_lca(int x,int y){
if (dep[x]<dep[y]) {
swap(x,y);
}
for (int i=21; i>=0; i--) {
if (dep[dp[x][i]]>=dep[y]) {
x=dp[x][i];
}
}
if (x==y) {
return x;
}
for (int i=21; i>=0; i--) {
if (dp[x][i]!=dp[y][i]) {
x=dp[x][i],y=dp[y][i];
}
}
return dp[x][0];
}
void dfs(int cur,int fa){
for (auto [v,w,e] : G[cur]) {
if (v==fa) {
continue;
}
dfs(v,cur);
diff[cur]+=diff[v];
}
}
bool check(int x){
tot=0;
memset(diff,0,sizeof diff);
for (int i=1; i<=m&&path[i].dis>x; i++,tot++) {
diff[path[i].u]++;
diff[path[i].v]++;
diff[path[i].lca]-=2;
}
if (!tot) {
return 1;
}
dfs(1,0);
int mx=-1e9;
for (int i=1; i<n; i++) {
if (diff[id[i]]==tot) {
mx=max(mx,w[i]);
}
}
return path[1].dis-mx<=x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
read(n),read(m);
int mxw=-1e9;
for (int i=1,u,v; i<n; i++) {
read(u),read(v),read(w[i]);
G[u].push_back({v,w[i],i});
G[v].push_back({u,w[i],i});
mxw=max(mxw,w[i]);
}
init_lca(1,0);
for (int i=1,u,v; i<=m; i++) {
read(path[i].u),read(path[i].v);
path[i].lca=get_lca(path[i].u,path[i].v);
path[i].dis=ddep[path[i].u]+ddep[path[i].v]-2*ddep[path[i].lca];
}
sort(path+1,path+m+1,cmp);
int l=path[1].dis-mxw-1,r=path[1].dis+1; //卡常 2
while (l+1<r) {
int mid=(l+r)>>1;
if (check(mid)) {
r=mid;
} else {
l=mid;
}
}
cout<<r;
return 0;
}
P8201
更加巧妙的一道题。
首先推式子，
令 \(dep_i\) 表示从根节点到 \(i\) 的路径上的点权异或和：
\[dis_{t,a} \oplus dis_{t,b}\\ =dep_a \oplus dep_b \oplus w_{lca} \oplus w_t\\ =k \]（\(dep_a \oplus dep_b\) 把 \(lca\) 的权值抵消了，要异或回来；\(t\) 本身应当被抵消，因此要再异或一次以抵消掉它）
也即：
\[dep_a \oplus dep_b \oplus w_{lca} \oplus k=w_t \]问题转化为有多少个点 \(t\) 满足上式。
我们将询问离线，然后一遍 dfs 统计出从根节点到每个点的路径上当前点权出现次数，询问时进行求一下 \(a \to son_{lca}\) 与 \(b \to lca\) 这两段的出现次数（前缀和），拼起来判断是否 \(>0\) 即可。
（对于树上信息问题，先推式子，接着求出从根节点出发的信息，然后利用前缀和 / 差分之类的东西维护）
code
//
// P8201.cpp
//
//
// Created by _XOFqwq on 2024/10/13.
//
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int a[N],b[N],lca[N],dep[N],dp[N][31];
long long k[N],w[N],dis[N];
vector<int> qry[N],G[N];
unordered_map<int,long long> cnt,ans[N];
void init_LCA(int cur,int fa){
dis[cur]=dis[fa]^w[cur];
dep[cur]=dep[fa]+1;
dp[cur][0]=fa;
for (int i=1; (1<<i)<=dep[cur]; i++) {
dp[cur][i]=dp[dp[cur][i-1]][i-1];
}
for (int i : G[cur]) {
if (i==fa) {
continue;
}
init_LCA(i,cur);
}
}
int get_LCA(int x,int y){
if (dep[x]<dep[y]) {
swap(x,y);
}
for (int i=21; i>=0; i--) {
if (dep[dp[x][i]]>=dep[y]) {
x=dp[x][i];
}
}
if (x==y) {
return x;
}
for (int i=21; i>=0; i--) {
if (dp[x][i]!=dp[y][i]) {
x=dp[x][i],y=dp[y][i];
}
}
return dp[x][0];
}
void dfs(int cur,int fa){
cnt[w[cur]]++;
for (int i : qry[cur]) {
ans[cur][i]=cnt[i];
}
for (int i : G[cur]) {
if (i==fa) {
continue;
}
dfs(i,cur);
}
cnt[w[cur]]--;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++) {
cin>>w[i];
}
for (int i=1,u,v; i<n; i++) {
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
init_LCA(1,0);
for (int i=1; i<=m; i++) {
cin>>a[i]>>b[i]>>k[i];
lca[i]=get_LCA(a[i],b[i]);
long long val=dis[a[i]]^dis[b[i]]^w[lca[i]]^k[i];
qry[a[i]].push_back(val);
qry[b[i]].push_back(val);
qry[lca[i]].push_back(val);
qry[dp[lca[i]][0]].push_back(val);
}
dfs(1,0);
for (int i=1; i<=m; i++) {
long long val=dis[a[i]]^dis[b[i]]^w[lca[i]]^k[i];
cout<<(ans[a[i]][val]-ans[lca[i]][val]+ans[b[i]][val]-ans[dp[lca[i]][0]][val]?"yEs\n":"nO\n");
}
return 0;
}