這個題目其實算是貪心吧，感覺自己貪心有點菜，這幾天要把貪心練一下了
建樹，dfs什么的就不說了，這里主要講下思路
就是建完樹后，給你兩個點
然后求出他們的lca，將這兩個點u,v和lca，dlca（lca點的深度）存在一個結構體數組中
然后將這個數組按深度從大到小排序
接著遍歷這個數組
每次看u,v有沒有訪問過，如果有就不管，如果沒有，就將他們的lca點拿掉并將lca點的所有子節點記為訪問過并且ans++
最后輸出ans就好了
其實，為什么這樣做可以呢
對于一個u,v，我們要做的就是把他們分開，我們就可以拿掉鏈接u,v上的點的任意一個就好，那么就會出現一個問題
如果有另外兩個點的lca正好經過這一條鏈，那么如果我只拿掉那個點的lca就好了
如果我們這樣排序的話，其實就保證了這種情況，也就是保證了最優
還有一點，我們標記已訪問過的點時，不需要用到樹鏈剖分，因為是對子樹的操作，dfs序就可以了
這個題目有點手殘，用的線段樹求的lca，代碼量直接爆炸了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 60010using namespace std;struct Edge
{int next,en;
};struct Save
{int node,dep;Save(int n,int d){node=n;dep=d;}Save(){}
};bool operator < (Save a,Save b)
{return a.dep<b.dep;}struct Node
{int u,v;Save lca;
};
bool operator < (Node a,Node b)
{return a.lca.dep<b.lca.dep;}bool cmp(Node a,Node b)
{return a.lca.dep>b.lca.dep;}Edge edge[maxn];
Node node[maxn];
Save save[maxn*2];
Save segt[maxn<<2];//線段樹的大小為節點大小的4倍int head[maxn],cnte;
int dfsx,in[maxn],out[maxn],vis[maxn],cntn;
int LCAArray[maxn*2];void init()
{memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));cnte=0;cntn=0;dfsx=0;
}void addedge(int st,int en)
{cnte++;edge[cnte].en=en;edge[cnte].next=head[st];head[st]=cnte;return;
}void addnode(int u,int v,Save lca)
{cntn++;node[cntn].u=u;node[cntn].v=v;node[cntn].lca=lca;return;
}void dfs(int root,int depth)//dfs沒問題
{dfsx++;in[root]=dfsx;vis[root]=1;save[dfsx].dep=depth;save[dfsx].node=root;for (int k=head[root];k!=-1;k=edge[k].next)if (!vis[edge[k].en]){dfs(edge[k].en,depth+1);dfsx++;save[dfsx].dep=depth;save[dfsx].node=root;}out[root]=dfsx;return;
}void build(int root,int beg,int en)//線段樹建樹函數
{if (beg==en)segt[root]=save[beg];else{build(root*2,beg,(beg+en)/2);build(root*2+1,(beg+en)/2+1,en);if (segt[root*2]<segt[root*2+1])segt[root]=segt[root*2];else segt[root]=segt[root*2+1];}return;
}Save query(int root,int l,int r,int ql,int qr)
{if(l == ql && r == qr) return segt[root];int mid=(l+r)/2;if(qr <= mid) return query(root*2,l,mid,ql,qr);else if(ql >= mid + 1) return query(root*2+1,mid+1,r,ql,qr);return min(query(root*2,l,mid,ql,mid), query(root*2+1,mid + 1,r,mid + 1,qr));
}void initLCA(int n)
{dfs(0,1);build(1,1,dfsx);
}Save LCA(int u,int v)
{int qbeg,qend;if (in[u]<in[v]){qbeg=in[u];qend=in[v];}else{qbeg=in[v];qend=in[u];}return query(1,1,dfsx,qbeg,qend);
}struct Segt
{int val,addmark;
};Segt segtf[maxn<<2];void pushdown(int root)
{if (segtf[root].addmark!=0){segtf[root*2].val+=segtf[root].addmark;segtf[root*2].addmark+=segtf[root].addmark;segtf[root*2+1].val+=segtf[root].addmark;segtf[root*2+1].addmark+=segtf[root].addmark;segtf[root].addmark=0;}return;
}int queryf(int root,int l,int r,int poi)
{if(l==r) return segtf[root].val;pushdown(root);int mid=(l+r)/2;if(poi <= mid) return queryf(root*2,l,mid,poi);else if(poi >= mid + 1) return queryf(root*2+1,mid+1,r,poi);
}void updatef(int root,int rst,int ren,int beg,int en,int val)
{if (rst>=beg&&ren<=en){segtf[root].val+=val;segtf[root].addmark+=val;}else if (rst>en||ren<beg) {return;}else{pushdown(root);int mid=(rst+ren)/2;updatef(root*2,rst,mid,beg,en,val);updatef(root*2+1,mid+1,ren,beg,en,val);segtf[root].val=segtf[root*2].val&&segtf[root*2+1].val;}
}int main()
{int n,m;while(~scanf("%d",&n)){init();for (int k=1;k<=n;k++){int st,en;scanf("%d %d",&st,&en);addedge(st,en);addedge(en,st);}n++;initLCA(n);scanf("%d",&m);for (int k=1;k<=m;k++){int u,v;Save lca;scanf("%d %d",&u,&v);lca=LCA(u,v);addnode(u,v,lca);}sort(node+1,node+1+cntn,cmp);memset(segtf,0,sizeof(segtf));int ans(0);for (int k=1;k<=cntn;k++){int u,v,l;u=node[k].u;v=node[k].v;l=node[k].lca.node;if ((queryf(1,1,dfsx,in[u])==0)&&(queryf(1,1,dfsx,in[v])==0)){ans++;updatef(1,1,dfsx,in[l],out[l],1);}}printf("%d\n",ans);}return 0;
}
總結
以上是生活随笔為你收集整理的HDU6203 补题LCA复习+dfs序的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
