不知道为什么,我这里poj打不开了。。。
这份题解只有在下无脑的口述(口胡),没有Code。3.30upd:现在有了。
题意:一棵有N个点的树,再往里面加入M条新边,现在要删掉两条边,要求一条是树边,一条是新边,求使图不连通方案的数量。
Solution:
同样的先考虑一条新边加入后,树上出现了一个环。
那么如果我们任意删掉不是这个环上的一条树边和这条新边,
可以发现,图仍然连通。
所以可以得到一个信息:
对与一条新边,我想要把它删掉,就必须把 把它加入后形成的环上的树边 给删掉。
换言之,就是只有删掉这样的树边,才会在删掉了这条新边的前提下,对答案造成贡献。
那么,
如果我们把 删一条新边 就必须删对应树边 中的这种对应关系,记为新边对树边的覆盖
反过来思考一下就成了:
对于每一条树边,我们只要算出它被多少新边覆盖,就可以计算答案了。
树上差分十分适合解决这种问题,只需稍微注意一下LCA处的处理即可。
关于答案统计:
对于不被新边覆盖的,贡献为新边条数。
只被一条新边覆盖的,贡献为1。
被大于等于二条新边覆盖的,贡献为0。
upd:感谢指出错误。
Code ↓:
#include#include #include #include #include #include #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 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