[POJ3417]Network【LCA+树形DP】

Network

【题目描述】

传送门

【题解】

我们考虑加入一条非树边(x,y),只会对x-LCA(x,y)-y上的树边造成影响,我们这里称(x,y)这条边覆盖了这条路径。
1.如果这条树边被覆盖了>=2次,那么不会做出贡献;
2.如果等于1,那么会有1点贡献;
3.如果等于0,那么会造成m点贡献;
问题是如何快速求出被覆盖的次数,这里可以借助前缀和的思想,Sum[x]++,Sum[y]++,Sum[LCA(x,y)]-=2,然后DFS便利求值就可以了。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n,m,Ans,Fa[MAXN][30],Dep[MAXN],Sum[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXN<<1],nxt[MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
void DFS(int x,int fa){
    Dep[x]=Dep[fa]+1;Fa[x][0]=fa;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(E.son[j]!=fa) DFS(E.son[j],x);
}
void DO(int x,int fa){
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=fa){
        DO(E.son[j],x),Sum[x]+=Sum[E.son[j]];
        if(Sum[E.son[j]]==0) Ans+=m;else
        if(Sum[E.son[j]]==1) Ans++;
    }
}
void init(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) Fa[i][j]=-1;
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) if(Fa[i][j-1]!=-1) Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}
int LCA(int p,int q){
    if(Dep[p]<Dep[q]) swap(p,q);
    int Del=Dep[p]-Dep[q];
    for(int i=0;(1<<i)<=Del;i++) if(Del&(1<<i)) p=Fa[p][i];
    if(p==q) return p;
    for(int i=log2(n);i>=0;i--)
    if(Fa[p][i]!=Fa[q][i]) p=Fa[p][i],q=Fa[q][i];
    return Fa[p][0];
}
int main(){
    n=read();m=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
    DFS(1,0),init();
    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),Sum[x]++,Sum[y]++,Sum[LCA(x,y)]-=2;
    DO(1,0);printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部