本文共 1622 字，大约阅读时间需要 5 分钟。
给定一棵树,每次删去叶子,有m个限制,分别为(a,b)表示a需要比b先删,为每个点能否成为最后被删的点
\(n,m \le 10^5\)
手模后会发现一个十分不显然的规律: 若a比b先删,则a在以b为根的子树中的点,都不能最后删,
于是这样就转化为这个题了:
每次直接打个差分标记
这题还要判无解的情况(这谁想得到啊)
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1using namespace std;typedef long long ll;const int mxn=5e5+5;int n,m,cnt,tot,in[mxn],hd[mxn],vis[mxn],hd2[mxn],sz[mxn],dep[mxn],ans[mxn],tag[mxn],dfn[mxn],f[mxn][19];inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f;}inline int chkmax(int &x,int y) {if(x y) x=y;}struct ed { int to,nxt;}t[mxn<<1];inline void add(int u,int v) { t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;}inline void add2(int u,int v) { t[++cnt]=(ed) {v,hd2[u]}; hd2[u]=cnt; ++in[v];}int up(int u,int k) { for(int i=30;i>=0;--i) if(k&(1< 0; for(int i=hd[u];i;i=t[i].nxt) { int v=t[i].to; if(v==fa) continue ; solve(v,u,val); }}int flag=0;void check() { queue q; for(int i=1;i<=n;++i) if(in[i]<2) q.push(i),vis[i]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=hd[u];i;i=t[i].nxt) { int v=t[i].to; --in[v]; if(!vis[v]&&in[v]<2) { vis[v]=1; q.push(v); } } for(int i=hd2[u];i;i=t[i].nxt) { int v=t[i].to; --in[v]; if(!vis[v]&&in[v]<2) { vis[v]=1; q.push(v); } } } for(int i=1;i<=n;++i) if(!vis[i]) flag=1; }int main(){ n=read(); m=read(); int u,v,w; for(int i=1;i dfn[u]&&dfn[v]
转载于:https://www.cnblogs.com/list1/p/10497916.html