NOI2021 輕重邊 題解
NOI2021 輕重邊
題目鏈接：#4812. [NOI2021] 輕重邊
前置知識 ： #樹鏈剖分 #線段樹
題目大意
給定\(n\)個點組成的樹，\(m\)次操作。
修改操作會讓路徑\(a \to b\)上的所有點的所有連邊對答案的貢獻變為\(0\)，路徑\(a \to b\)的所有邊的貢獻變為\(1\)；
查詢操作則統計路徑\(a \to b\)的答案貢獻。(樹中一開始答案貢獻為\(0\))。
輸入格式
第\(1\)行，輸入\(T\)，表示有\(T\)組數據。
每組數據
第\(1\)行，輸入\(n,m\)表示有\(n\)個點和\(m\)個操作。
第\(2-n\)行，每行輸入\(u,v\)表示樹的一條邊。
第\(n+1-n+m\)行，每行輸入\(op,a,b\)表示操作信息\((op=1為修改，op=2為查詢)\)
輸入樣例
1
7 7
1 2
1 3
3 4
3 5
3 6
6 7
1 1 7
2 1 4
2 2 7
1 1 5
2 2 7
1 2 1
2 1 7
輸出樣例
1
3
2
1
數據范圍
對于所有測試數據:\(T≤3，1≤n,m≤10^5\)。
| 測試點編號 | \(n,m \le\) | 特殊性質 |
|---|---|---|
| \(1 \sim 2\) | \(10\) | 無 |
| \(3 \sim 6\) | \(5000\) | 無 |
| \(7 \sim 8\) | \(10^5\) | \(A,B\) |
| \(9 \sim 10\) | \(10^5\) | \(A\) |
| \(11 \sim 14\) | \(10^5\) | \(B\) |
| \(15 \sim 16\) | \(2 \times 10^4\) | 無 |
| \(17 \sim 20\) | \(10^5\) | 無 |
思考
感覺每次修改操作對答案的貢獻是單獨的，前面的修改操作不會影響的后面修改操作對答案的貢獻 (就是不會讓后面的操作與前面的操作產生額外貢獻)。
比如樣例
經過第一個操作后\(\Huge \downarrow\)
所以操作具有無后效性，如果后面的操作與前面的操作重合，那么會統計后面的操作貢獻，前面的操作會無效。
所以我們只需要單獨考慮每一次修改操作，使其擁有單獨的統計答案的方式。
那么可以給每個修改操作路徑上的點打上時間戳，若邊連接兩點的時間戳相同，則該邊的貢獻為 \(1\) ，否則為 \(0\) 。
可以簡單證明一下操作的正確性，每次修改操作會讓路徑 \(a \to b\) 上的所有點的所有連邊對答案的貢獻變為 \(0\)，路徑 \(a \to b\) 的所有邊的貢獻變為 \(1\) ，就相當于把這一條鏈單獨拎出來，將其邊權修改為 \(1\) 。
而將這條鏈打上單獨的時間戳，既可以起到方便統計答案的作用，又可以和其它修改操作進行區分。然后為了實現后面操作對前面操作的覆蓋，我們只記錄節點當前的時間戳。
然后統計答案的操作
兩個相同的點權貢獻答案，感覺和「SDOI2011」染色有點像，不同的是這道題每兩個點時間戳相同就貢獻一次，而染色是每兩個點時間戳不同就貢獻一次。
部分分1
#樹 #LCA
對于前\(1\sim 6\)個測試點，\(n,m \le 5000\)，完全可以接受 \(\mathcal{O}(n \cdot m)\) 的時間復雜度。
直接進行暴力修改每個節點的時間戳和遍歷整棵樹統計答案即可。
時間復雜度 \(\mathcal{O}(T \cdot nm)\) 期望得分\((30 \ points)\) (實際上因為常數小第\(15-16\)個點也可以過) (實際得分 \(40 \ points\))
關鍵代碼
//倍增求lca
void dfs(int x,int fa){
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(int i=1;i<20;i++){
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=h[x];i;i=e[i].nex){
int v=e[i].to;
if(v==fa){
continue;
}
dfs(v,x);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=19;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){
x=f[x][i];
}
}
if(x==y){
return x;
}
for(int i=19;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
//修改操作，枚舉每個點暴力修改
if(op==1){
int LCA=lca(a,b);
c++;
for(int i=a;i!=LCA;i=f[i][0]){
w[i]=c;
}
for(int i=b;i!=LCA;i=f[i][0]){
w[i]=c;
}
w[LCA]=c;
}
//查詢操作，枚舉每個點暴力判斷
if(op==2){
int LCA=lca(a,b);
int ans=0;
for(int i=a;i!=LCA;i=f[i][0]){
if(w[i]&&w[i]==w[f[i][0]]){
ans++;
}
}
for(int i=b;i!=LCA;i=f[i][0]){
if(w[i]&&w[i]==w[f[i][0]]){
ans++;
}
}
printf("%d\n",ans);
}
部分分2
#線段樹 #DFS序
對于\(7 \sim 10\)個測試點，樹的形態是一條鏈，那么我們直接用\(DFS序\)的方式將樹轉為區間問題，直接用線段樹維護即可。
時間復雜度 \(\mathcal{O}(T \cdot m \log_2 n)\)
我們把操作放在區間上來分析是如何合并的。
設 \(w[i]\) 代表第 \(i\) 點的時間戳，\(s[i]\) 表示線段樹的點 ，我們設 \(s[i].l \ 和 \ s[i].r \ 分別為 \ s[i]\) 代表的區間左右端點，而 \(s[i]\) 的信息會從\(s[2*i] \ 和 \ s[2*i+1] \ 轉移過來\) 。
我們在 [[#思考]] 中已經提到過每兩個點相同就貢獻一次，而兩個子節點內部已經統計過，直接轉移即可。
會產生變化的只有兩個子節點交界的地方，所以我們需要記錄區間左右端點的時間戳，進行判斷。
struct tree{
int l=0;//區間左端點
int r=0;//區間右端點
int lx=0;//區間左端點顏色
int rx=0;//區間右端點顏色
int lazy=0;//懶標記
int w=0;//區間內答案貢獻
tree operator +(const tree&a)const{//重載運算符，區間合并
tree res;
res.l=l;
res.lx=lx;//左兒子的左端點是區間左端點
res.r=a.r;
res.rx=a.rx;//右兒子的右端點是區間右端點
res.w=w+a.w;
if(rx==a.lx&&rx){//warning 當沒有時間戳時不統計答案
res.w++;
}
return res;
}//warning 記住結構體中的每個元素都要賦值，就算不變也要在賦值一遍，因為使用時是直接s[k]=s[ls]+s[rs]的賦值操作，如果不每個元素都要賦值可能導致使用的值丟失，讓程序錯誤。
}s[500050];
關鍵代碼
//求DFS序
void dfs(int x,int fa){
dfn[x]=++num;
rk[num]=x;
for(int i=h[x];i;i=e[i].nex){
int v=e[i].to;
if(v==fa){
continue;
}
dfs(v,x);
}
}
//線段樹維護
void build(int k,int l,int r){
s[k].l=l;
s[k].r=r;
if(l==r){
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
s[k]=s[k<<1]+s[k<<1|1];
}
//修改
void change(int k,int x,int y,int z){
if(x<=s[k].l&&s[k].r<=y){
s[k].w=s[k].r-s[k].l;
s[k].ls=s[k].rs=s[k].lazy=z;
return;
}
pushdown(k);//warning 不要忘了下放懶標記
if(x<=s[k<<1].r){
change(k<<1,x,y,z);
}
if(y>=s[k<<1|1].l){
change(k<<1|1,x,y,z);
}
s[k]=s[k<<1]+s[k<<1|1];
}
//詢問
tree query(int k,int x,int y){
if(x<=s[k].l&&s[k].r<=y){
return s[k];
}
pushdown(k);//warning 不要忘了下放懶標記
if(y<=s[k<<1].r){//如果區間全在左子樹，就只在左子樹上查找
return query(k<<1,x,y);
}
if(s[k<<1|1].l<=x){//同理
return query(k<<1|1,x,y);
}
return query(k<<1,x,y)+query(k<<1|1,x,y);
}
\(std\)
#樹鏈剖分 #線段樹
根據部分分2，線段樹可以維護一條鏈，那么就自然的想到了把樹變成鏈的算法樹鏈剖分，樹剖剖成多條重鏈用線段樹進行維護。
時間復雜度 \(\mathcal{O}(T \cdot m\log^2_2 n)\)
\(Code\)
#include<bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
inline long long read(){
long long x=0,w=0;char c=0;
while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
int n,m,x,y,z,t,cnt;
int son[100050],siz[100050],f[100050],dep[100050],dfn,id[100050],rk[100050],top[100050];
vector<int> mp[100050];
char op;
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;
siz[x]=1;
f[x]=fa;
for(int i:mp[x]){
if(i==fa){
continue;
}
dfs1(i,x);
siz[x]+=siz[i];
if(siz[son[x]]<siz[i]){
son[x]=i;
}
}
}
void dfs2(int x,int root){
id[x]=++dfn;
rk[dfn]=x;
top[x]=root;
if(son[x]){
dfs2(son[x],root);
}
for(int i:mp[x]){
if(i==f[x]||i==son[x]){
continue;
}
dfs2(i,i);
}
}
//樹鏈剖分
struct tree{
int l=0;
int r=0;
int lx=0;
int rx=0;
int lazy=0;
int w=0;
tree operator +(const tree&a)const{
tree res;
res.l=l;
res.r=a.r;
res.lx=lx;
res.rx=a.rx;
res.w=w+a.w;
if(rx==a.lx&&rx){
res.w++;
}
return res;
}
}s[500050];
void pushup(int k){
s[k]=s[ls]+s[rs];
}
void pushdown(int k){
if(!s[k].lazy){
return;
}
s[ls].lazy=s[ls].lx=s[ls].rx=s[rs].lazy=s[rs].lx=s[rs].rx=s[k].lazy;
s[ls].w=s[ls].r-s[ls].l;
s[rs].w=s[rs].r-s[rs].l;
s[k].lazy=0;
}
void build(int k,int l,int r){
s[k].l=l;
s[k].r=r;
if(s[k].l==s[k].r){
s[k].w=s[k].lazy=s[k].lx=s[k].rx=0;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(k);
}
void change(int k,int x,int y,int c){
if(x<=s[k].l&&s[k].r<=y){
s[k].lx=s[k].rx=s[k].lazy=c;
s[k].w=s[k].r-s[k].l;
return;
}
pushdown(k);
if(x<=s[ls].r){
change(ls,x,y,c);
}
if(s[rs].l<=y){
change(rs,x,y,c);
}
pushup(k);
}
tree query(int k,int x,int y){
if(x<=s[k].l&&s[k].r<=y){
return s[k];
}
pushdown(k);
if(y<=s[ls].r){
return query(ls,x,y);
}
if(s[rs].l<=x){
return query(rs,x,y);
}
return query(ls,x,y)+query(rs,x,y);
}
//線段樹維護
void solve1(){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy]){
swap(x,y);
swap(fx,fy);
}
change(1,id[fx],id[x],z);
x=f[fx];
fx=top[x];
}
if(id[x]>id[y]){
swap(x,y);
}
change(1,id[x],id[y],z);
}
//修改
void solve2(){
int fx=top[x],fy=top[y];
tree ansx=(tree){0,0,0,0,0,0},ansy=(tree){0,0,0,0,0,0};
while(fx!=fy){
if(dep[fx]>dep[fy]){
ansx=query(1,id[fx],id[x])+ansx;
x=f[fx],fx=top[x];
}
else{
ansy=query(1,id[fy],id[y])+ansy;
y=f[fy],fy=top[y];
}
}
if(id[x]>id[y]){
ansx=query(1,id[y],id[x])+ansx;
}
else{
ansy=query(1,id[x],id[y])+ansy;
}
swap(ansx.lx,ansx.rx);
ansx=ansx+ansy;
printf("%d\n",ansx.w);
}
//查詢
int main(){
t=read();
while(t--){
n=read();
m=read();
memset(son,0,sizeof(son));
memset(siz,0,sizeof(siz));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
mp[i].clear();
}
for(int i=1;i<n;i++){
x=read();
y=read();
mp[x].push_back(y);
mp[y].push_back(x);
}
dfn=0,cnt=0;
dfs1(1,0);
dfs2(1,1);
build(1,1,dfn);
for(int i=1;i<=m;i++){
cin>>op;
x=read();
y=read();
if(op=='1'){
z=++cnt;//時間戳變化
solve1();
}
else{
solve2();
}
}
}
return 0;
}
\(Warning\)
樹鏈剖分的查詢部分有一些難以理解和容易出錯 (因為要注意合并的順序) ，特此圖解。
聚焦代碼
void solve2(){
int fx=top[x],fy=top[y];
tree ansx=(tree){0,0,0,0,0,0},ansy=(tree){0,0,0,0,0,0};
while(fx!=fy){
if(dep[fx]>dep[fy]){
ansx=query(1,id[fx],id[x])+ansx;//聚焦點1
x=f[fx],fx=top[x];
}
else{
ansy=query(1,id[fy],id[y])+ansy;//聚焦點1
y=f[fy],fy=top[y];
}
}
if(id[x]>id[y]){
ansx=query(1,id[y],id[x])+ansx;//聚焦點1
}
else{
ansy=query(1,id[x],id[y])+ansy;//聚焦點1
}
swap(ansx.lx,ansx.rx);//聚焦點2
ansx=ansx+ansy;
printf("%d\n",ansx.w);
}
\(ansx \ 和 \ ansy \ 中只需注意轉移 \ lx,rx,w \ 的值\)
圖例
箭頭表示跳躍的路程
加粗的點為重鏈的 \(top\)
數字為節點的時間戳
因為\(dep[fy]>dep[x]\)
所以
聚焦點1
因為\(id[x]>id[y]\)
所以
因為\(query()\)表示
而\(x\)在\(7\)
\(ansx\)往上跳
所以為 \(ansx=query()+ansx\)
\(ansy同理\)
然后是最后的合并，\(x,y都在同一個節點上\)
聚焦點2
這時候我們發現， \(ansx.lx\) 表示的為 \(3\) 的時間戳，\(ansy.lx\)表示的為 \(4\) 的時間戳，而根據我們的合并。
tree operator +(const tree&a)const{//重載運算符，區間合并
tree res;
res.l=l;
res.lx=lx;//左兒子的左端點是區間左端點
res.r=a.r;
res.rx=a.rx;//右兒子的右端點是區間右端點
res.w=w+a.w;
if(rx==a.lx&&rx){//統計相鄰點的答案 warning 當沒有時間戳時不統計答案
res.w++;
}
return res;
}
應該是\(ansx.rx\)和\(ansy.lx\)表示相鄰點的時間戳。
所以我們需要 \(swap(ansx.lx,ansx.rx)\)再進行 \(ansx=ansx+ansy\)
浙公網安備 33010602011771號