湖州猪八戒做网站,wordpress友情链接,那非西,内衣网站建设推广正题
题目链接:https://www.luogu.com.cn/problem/P4494 题目大意
给出nnn个点mmm条边的一张无向图#xff0c;节点有0/10/10/1#xff0c;每条边可以选择是否取反两边的点。
开始求将所有节点变为000的方案#xff0c;然后对于每个点询问删去这个点之后的方案 1≤T≤5,1…正题
题目链接:https://www.luogu.com.cn/problem/P4494 题目大意
给出nnn个点mmm条边的一张无向图节点有0/10/10/1每条边可以选择是否取反两边的点。
开始求将所有节点变为000的方案然后对于每个点询问删去这个点之后的方案
1≤T≤5,1≤n,m≤1051\leq T\leq 5,1\leq n,m\leq 10^51≤T≤5,1≤n,m≤105 解题思路
图的比较麻烦先考虑树上的那么每条边取不取反取决于它连接的子节点的黑白但是根节点却无法这么调整。所以如果黑色个数为奇数个那么方案为000否则方案为111。
然后考虑一张连通图考虑对于图中的一个生成树来说无论非生成树上的边是否取反都可以用这棵生成树调整回来也就是如果黑色为奇数个方案为000否则方案为2m−n12^{m-n1}2m−n1。
因为原图不一定连通设连通块个数为kkk那么第一问答案就是2m−nk2^{m-nk}2m−nk每个连通块的黑色个数为奇数个。
然后第二问其实就是去掉这条边之后会分割一个连通块以影响答案。
建立广义圆方树统计每个点删去后会多产生的连通块数量以及是否有分割出来的连通块的黑色个数为奇数。
顺带一提的是需要特判如果有两个或者以上的连通块黑色为奇数个那么全都无解否则只有可能删除掉黑色奇数连通块里的点。
时间复杂度O(Tn)O(Tn)O(Tn) code
#includecstdio
#includecstring
#includealgorithm
#includestack
#includevector
#define ll long long
using namespace std;
const ll N2e510,P1e97;
ll Z,n,m,dfc,sum,cnt,st[N],deg[N];
ll dfn[N],low[N],pw[N],siz[N];
bool tag[N],nok[N],v[N];
stackll s;char t[N];
vectorllG[N],T[N];
void tarjan(ll x){dfn[x]low[x]dfc;sum(t[x]1);s.push(x);st[st[0]]x;for(ll i0;iG[x].size();i){ll yG[x][i];if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);if(low[y]dfn[x]){ll k;cnt;do{ks.top();s.pop();deg[k]--;T[cnt].push_back(k);T[k].push_back(cnt);}while(k!y);T[cnt].push_back(x);T[x].push_back(cnt);deg[x]--;}}else low[x]min(low[x],dfn[y]);}return;
}
void dfs(ll x){v[x]1;st[st[0]]x;siz[x](xn)(t[x]1);for(ll i0;iT[x].size();i){ll yT[x][i];if(v[y])continue;dfs(y);siz[x]siz[y];if(siz[y]1)nok[x]1;}return;
}
signed main()
{scanf(%lld,Z);pw[0]1;for(ll i1;iN;i)pw[i]pw[i-1]*2%P;while(Z--){dfc0;memset(deg,0,sizeof(deg));memset(nok,0,sizeof(nok));memset(tag,0,sizeof(tag));memset(dfn,0,sizeof(dfn));memset(v,0,sizeof(v));while(!s.empty())s.pop();scanf(%lld%lld,n,m);for(ll i1;i2*n;i)T[i].clear(),G[i].clear();for(ll i1;im;i){ll x,y;scanf(%lld%lld,x,y);G[x].push_back(y);deg[x];G[y].push_back(x);deg[y];}scanf(%s,t1);cntn;ll one0,k0;for(ll i1;in;i){if(dfn[i])continue;st[0]sum0;tarjan(i);k;if(sum1){for(ll j1;jst[0];j)tag[st[j]]1;one;}}if(one1){for(ll i0;in;i)printf(0 );putchar(\n);continue;}else if(one)printf(0 );else printf(%lld ,pw[m-nk]);for(ll i1;in;i){if(v[i])continue;st[0]0;dfs(i);for(ll j1;jst[0];j)if((siz[i]-siz[st[j]])1)nok[st[j]]1;}for(ll i1;in;i)if(nok[i]||(one!tag[i]))printf(0 );else printf(%lld ,pw[m-nk-deg[i]]);putchar(\n);}return 0;
}
