POJ3417Network 樹上差分。

POJ3417Network

不知道為什麼，我這裡poj打不開了。。。

這份題解隻有在下無腦的口述（口胡），沒有Code。3.30upd：現在有了。

題意：一棵有N個點的樹，再往裡面加入M條新邊，現在要删掉兩條邊，要求一條是樹邊，一條是新邊，求使圖不連通方案的數量。

Solution：

同樣的先考慮一條新邊加入後，樹上出現了一個環。

那麼如果我們任意删掉不是這個環上的一條樹邊和這條新邊，

可以發現，圖仍然連通。

是以可以得到一個資訊：

對與一條新邊，我想要把它删掉，就必須把 把它加入後形成的環上的樹邊 給删掉。

換言之，就是隻有删掉這樣的樹邊，才會在删掉了這條新邊的前提下，對答案造成貢獻。

那麼，

如果我們把 删一條新邊 就必須删對應樹邊 中的這種對應關系，記為新邊對樹邊的覆寫

反過來思考一下就成了：

對于每一條樹邊，我們隻要算出它被多少新邊覆寫，就可以計算答案了。

樹上差分十分适合解決這種問題，隻需稍微注意一下LCA處的處理即可。

關于答案統計：

對于不被新邊覆寫的，貢獻為新邊條數。

隻被一條新邊覆寫的，貢獻為1。

被大于等于二條新邊覆寫的，貢獻為0。

upd：感謝神犇chd指出錯誤。

Code ↓：

#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double 
using namespace std;

IL int gi() {
    char ch=getchar(); RG int x=0,q=0;
    while(ch<'0'||ch>'9') q=ch=='-'?1:q,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return q?-x:x;
}

const int N=2e5+10;

vector<int> ver[N<<1],id[N<<1];
int n,m,num,ans,tot,head[N],inp[N][2],fa[N],vis[N],LCA[N],val[N];

struct EDGE{int next,to;}e[N<<1];
IL void make(int x,int y) {
    e[++tot]=(EDGE){head[x],y},head[x]=tot;
    e[++tot]=(EDGE){head[y],x},head[y]=tot; 
}

IL void Input(int dir,int x,int y) {
    inp[dir][0]=x,inp[dir][1]=y;
    if (x==y) return;
    ver[x].push_back(y),id[x].push_back(dir);
    ver[y].push_back(x),id[y].push_back(dir);   
}

int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}

void Tarjan(int x,int fx) {
    RG int i,y,Id;
    for (i=head[x],vis[x]=1;i;i=e[i].next)
        if ((y=e[i].to)!=fx) Tarjan(y,x),fa[y]=x;
    for (i=0;i<ver[x].size();++i) {
        y=ver[x][i],Id=id[x][i];
        if (vis[y]==2) LCA[Id]=getfa(y);
    }
    vis[x]=2;
}

void dfs(int x,int fx) {
    RG int i,y;
    for (i=head[x];i;i=e[i].next)
        if ((y=e[i].to)!=fx) dfs(y,x),val[x]+=val[y];
}

int main ()
{
    RG int i,x,y;
    n=gi(),m=gi();
    for (i=1;i<n;++i) x=gi(),y=gi(),make(x,y);
    for (i=1;i<=m;++i) x=gi(),y=gi(),Input(i,x,y);
    for (i=1;i<=n;++i) fa[i]=i;
    for (i=1,Tarjan(1,0);i<=m;++i) {
        x=inp[i][0],y=inp[i][1];
        if (x==y) continue;
        ++val[x],++val[y],val[LCA[i]]-=2;
    }
    for (i=2,dfs(1,0);i<=n;++i)
        if (val[i]==1) ++ans;
        else if (!val[i]) ans+=m;
    printf("%d\n",ans);
    return 0;
}

// 問題轉化+樹上差分
                

The End

轉載于:https://www.cnblogs.com/Bhllx/p/10616897.html