Bytedance 2019 icpc Camp day4 b组 H Network（树上差分+路径

2019-04-14 08:56发布

站内文章 / 模拟电子
13114 0 1373
题意：有一个n个点m条边的无向图，需要任意割两条边使图不连通。求方案数。 假设我们有了图的任意一个生成树，易知答案一共由三个部分贡献
  1. 如果某两个点只被某两条边同时覆盖，那么同时删去这两条边；
  2. 如果任意一条由根出发的路径上，如果任意两条树边它们被其他边覆盖情况是一样的，那么我们可以把这两条树边删去中间部分就会变得与原图不连通；
  3. 桥+任意一条边。
其中1和3只要随便做一次树上差分跑个dfs就可以统计贡献。难点是我们如何维护任意树边被其他边的覆盖情况。 我们可以对路径hash
  • 像查分一样在路径两端+-上一个随机值，或者同时亦或上一个随机值（推荐使用后者，加和太容易冲突了）。
  • 两个树边的权值如果相同那么它们的被其他边覆盖的情况是一样的。
把上述情况全部加起来就是最终结果了。 #include #include #include #include #include #include #include #include #include #include #include #include #define qcin; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define pb push_back #define mp make_pair #define clr(x) memset(x,0,sizeof x) #define fmax(x) memset(x,0x3f,sizeof x) #define finit(x) memset(x,-1,sizeof x) #define dis(l,r) r-l+1 #define gstr(str) scanf("%s",str) #define glen(str) strlen(str) using namespace std; typedef long long ll; namespace Input { const int BUF = 65536; char buf[BUF + 1]; char *head = buf, *tail = buf; } inline char inputchar() { using namespace Input; if(head == tail) *(tail = (head = buf) + fread(buf, 1, BUF, stdin)) = 0; return *head++; } inline void io(int &ret){ char ch = inputchar(); while(ch < '0' || ch > '9') ch = inputchar(); ret = ch - '0'; ch = inputchar(); while(ch >= '0' && ch <= '9'){ ret = ret * 10 + ch - '0'; ch = inputchar(); } } inline void sio(int &ret){ ret = 0; char ch = inputchar(); while((ch < '0' || ch > '9') && ch != '-') ch = inputchar(); bool neg = false; if(ch == '-') neg = true, ch = inputchar(); while(ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; ch = inputchar(); } if(neg) ret = -ret; } typedef pairpll; const int maxn = 5e5+10; const ll mo = 2148473648; typedef ll arr[maxn]; typedef char str[maxn]; void file(int x){if(x&&fopen("in.txt","r")){freopen("in.txt","r",stdin);if(x==2)freopen("1.txt","w",stdout);}} struct Edge{ int to,cst,nxt; }E[maxn*10]; const double pi=acos(-1); arr dfn,id,h,fa,dep,tree,num,hsh,a; int n,tot,pos,m,st,cnt,bri; void addedge(ll h[],int u,int v,int w=0){ E[tot].to=v; E[tot].cst=w; E[tot].nxt=h[u]; h[u]=tot++; } struct node { int u,v; }e[maxn]; void dfs(int x,int d){ dfn[x]=++pos,id[pos]=x;dep[x]=d; for(int i=h[x];~i;i=E[i].nxt){ int y=E[i].to; if(!dfn[y]){ tree[i>>1]=1; fa[y]=x; dfs(y,d+1); } } } void init(){ clr(dfn);clr(tree); clr(num);clr(hsh); finit(h); tot=0;pos=0; cnt=0;bri=0; } unsigned long long last=0; ll gethash(){ last=(rand()*rand()<<2)+rand()+last; ll res=(last>>1); return res; } int main(){ file(1); srand(time(NULL)); int u,v,w; io(n),io(m); init(); for(int i=0;idep[v])swap(u,v); ll w=gethash(); assert(w>=0); num[u]--;hsh[u]^=w; num[v]++;hsh[v]^=w; } ll now=0,ans=0; for(int i=pos;i>1;i--){ int p=id[i]; num[fa[p]]+=num[p]; hsh[fa[p]]^=hsh[p]; if(!num[p])bri++; else { ans+=(num[p]==1); a[now++]=hsh[p]; } } sort(a,a+now); ll tmp=1; for(int i=1;i  

热门文章