刚学圆方树 10s
查看原帖
刚学圆方树 10s
538609
Neutralized楼主2022/12/14 16:06

全 T 了(,感觉很神奇啊!
写得很丑,就是把圆方树建出来然后每次扫一遍虚树求边权和,不知道哪里写错了。

#include <bits/stdc++.h>
using namespace std;

#define ri register int
#define ll long long
#define Tp template<class T>
namespace SlowIO{
	const int End=1e6; static char outp[End],buf[End],*p1=buf,*p2=buf; //inline char getchar(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,End,stdin),p1==p2)?EOF:*p1++; }
	Tp inline void rd(T &x,char i=getchar(),bool f=0){ x=0; while(i<48||i>57) f|=i=='-',i=getchar(); while(i>=48&&i<=57) x=(x<<3)+(x<<1)+(i^48),i=getchar(); f&&(x=-x); } Tp inline void op(T x,int out=0){ if(!x){ putchar(48); return; } x<0&&(x=-x,putchar('-')); while(x) outp[++out]=(x%10)^48,x/=10; while(out) putchar(outp[out--]); } Tp inline void writeln(T x){ op(x),putchar('\n'); } Tp inline void writesp(T x){ op(x),putchar(' '); } Tp inline void write(T x,char c=0){ op(x); c&&putchar(c); }
}; using namespace SlowIO;

const int N = 400003;
int n,m,q,dfn[N],low[N],Dfn,sta[N],Top,tot,val[N],dep[N],son[N],siz[N],top[N],fa[N],nd[N],cnt,sum[N],idx,S[N],E[N];
struct Graph{
	int head[N],cntr;
	inline void Clr(){ memset(head,0,sizeof(head)),cntr=1; }
	struct edge{ int frm,to,nxt; }e[N<<1];
	inline void add(int u,int v){ e[++cntr]={u,v,head[u]},head[u]=cntr; }
	inline void Add(int u,int v){ add(u,v),add(v,u); }
}G,T; vector<int> vec[N]; bitset<N> vis;
#define gfore(u,A) for(int i=A.head[u],v;i;i=A.e[i].nxt)

inline void Tarjan(int u,int lst){
	dfn[u]=low[u]=++Dfn;
	gfore(u,G) if(i!=(lst^1)){
		v=G.e[i].to; if(!dfn[v]){
			sta[++Top]=i,Tarjan(v,i),low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) --Top,T.Add(u,v);
			else if(low[v]==dfn[u]){
				++tot; while(Top){
					int t=sta[Top],now=G.e[t].frm;
					--Top,vec[tot].emplace_back(now);
					if(t==i) break;
				} for(int x:vec[tot]) T.Add(tot,x);
			}
		} else if(dfn[v]<dfn[u]) sta[++Top]=i,low[u]=min(low[u],dfn[v]);
	}
}

inline void DFS(int u,int father){ dep[u]=dep[fa[u]=father]+1,sum[u]=sum[fa[u]]+(u<=n),siz[u]=1; gfore(u,T) if((v=T.e[i].to)!=fa[u]) DFS(v,u),siz[u]+=siz[v],son[u]=siz[son[u]]<siz[v]?v:son[u]; }
inline void ATTLAS(int u,int tp){ top[u]=tp,S[u]=++idx; if(son[u]) ATTLAS(son[u],tp); gfore(u,T) if((v=T.e[i].to)!=fa[u]&&v!=son[u]) ATTLAS(v,v); E[u]=++idx; }
inline int LCA(int a,int b){ while(top[a]^top[b]){ if(dep[top[a]]<dep[top[b]]) swap(a,b); a=fa[top[a]]; } return dep[a]<dep[b]?a:b; }

main(){
	auto Cmp = [](int a,int b){ return (a<0?E[-a]:S[a])<(b<0?E[-b]:S[b]); };

	int Te; rd(Te); while(Te--){
		memset(dfn,0,sizeof(dfn));
		for(int i=n+1;i<=tot;++i) vec[i].clear();
		rd(n),rd(m),tot=n,G.Clr(),T.Clr(),Dfn=Top=idx=0;
		for(int i=1,u,v;i<=m;++i) rd(u),rd(v),G.Add(u,v);
		rd(q),Tarjan(1,0),DFS(1,0),ATTLAS(1,1);
		while(q--){
			rd(cnt); vector<int> tmp; int res=0,sav=cnt;
			for(int i=1;i<=cnt;++i) rd(nd[i]),vis[nd[i]]=1;
			sort(nd+1,nd+cnt+1,Cmp);
			for(int i=1;i<cnt;++i){ int lca = LCA(nd[i],nd[i+1]); if(!vis[lca]) vis[lca]=1,tmp.emplace_back(lca); }
			for(int i=1;i<=cnt;++i) nd[i+cnt]=-nd[i]; cnt<<=1;
			for(int x:tmp) nd[++cnt]=x,nd[++cnt]=-x;
			sort(nd+1,nd+cnt+1,Cmp); stack<int> Sta;
			for(int i=1;i<=cnt;++i) if(nd[i]<0){
				int u = Sta.top(); Sta.pop(),vis[u]=0;
				if(Sta.size()) res+=sum[u]-sum[Sta.top()]; else res+=u<=n;
			} else Sta.push(nd[i]); writeln(res-sav);
		}
	}
}
2022/12/14 16:06
加载中...