《洛谷P5157 [USACO18DEC]The Cow Gathering P》

首先,这题要对题意先进行一个转化。

可以发现,这是一棵树,并且,我们要删点,肯定要从叶子节点开始删,才能保证在大于2个点时。

每个点最少存在一个朋友。

那么,我们主要要去分析,当我们加入关系边时,有哪些点无法作为最后点了(如果没有关系边,那么从一个点两边删,肯定每条边都会满足)

从遥远的国度借鉴经验。

我们以1为根来考虑换根后的贡献变化。

当a不在1->b的链上时。那么只有a的子树无法,作为最后点。

因为a要比b先删,那么a的子树肯定要比a先删,就算不先删也肯定会断开了。

当a在1->b的链上时。除了a往b方向的子节点z的子树,其他的都无法作为最后点。(和上面差不多地思考一下就行)

所以,我们只需要判断位置,然后对于不合法的点进行加1,如果最后点的权值<=0,说明合法。

这里用dfs序差分来高效加值,因为dfs对于子树是连续的,所以可以直接差分,然后最后求一下前缀和即可。

这里,还需要思考一个问题:是否存在无解的情况。

事实上,我们可以发现,当存在环时,对于环上的点,即要比对方先删,又要对方比自己先删,肯定无法实现,那么相对的所有点都无法实现了。

所有,我们需要判断是否存在环。这里拓扑来判环。

注意的是,我们要对关系边,新建图,然后拓扑时同时去两张图拓扑。

然后我们在无向边时也要统计入度,然后对于叶子就是入度<2的点了(一开始是1,当后面可能<1)。

如果只对关系边统计如果,很可能不是叶子节点的点也入度 == 0,所以要这样统计

《洛谷P5157 [USACO18DEC]The Cow Gathering P》
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<LL,int> pii;
const int N = 1e5+5;
const int M = 2e6+5;
const LL Mod = 998244353;
#define rg register
#define pi acos(-1)
#define INF 1e18
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
int n,m,in[N];
vector<int> G[N],vec[N];
int id[N],rk[N],dep[N],ssize[N],f[N][25],lg[N],c[N],vis[N],ans[N],tim = 0;
void init()
{
    for(int i = 1;i < N;++i) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i);
}
void dfs(int u,int fa)
{
    dep[u] = dep[fa]+1;
    f[u][0] = fa,ssize[u] = 1;
    id[u] = ++tim,rk[tim] = u;
    for(rg int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1];
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        ssize[u] += ssize[v];
    }
}
int LCA(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y])
    {
        x = f[x][lg[dep[x]-dep[y]]-1];
    }
    if(x == y) return x;
    for(rg int i = lg[dep[x]]-1;i >= 0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}
int Get_fa(int x,int k)
{
    for(int i = 24;i >= 0;--i)
    {
        if(k >= (1<<i)) x = f[x][i],k -= (1<<i);
    }
    return x;
}
bool slove()
{
    queue<int> 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(auto v : vec[u])
        {
            in[v]--;
            if(in[v] < 2 && !vis[v])
            {
                vis[v] = 1;
                Q.push(v);
            }
        }
        for(auto v : G[u])
        {
            in[v]--;
            if(in[v] < 2 && !vis[v])
            {
                vis[v] = 1;
                Q.push(v);
            }
        }
    }
    for(int i = 1;i <= n;++i) if(!vis[i]) return false;
    return true;
}
int main()
{
    init();
    n = read(),m = read();
    for(int i = 1;i < n;++i)
    {
        int x,y;x = read(),y = read();
        G[x].push_back(y);
        G[y].push_back(x);
        in[x]++,in[y]++;
    }
    dfs(1,0);
    while(m--)
    {
        int a,b;a = read(),b = read();
        if(LCA(a,b) == a)
        {
            int xx = Get_fa(b,dep[b]-dep[a]-1);
           // dbg(xx);
            c[1]++,c[id[xx]]--;
            c[id[xx]+ssize[xx]]++,c[n+1]--;
        }
        else
        {   
            c[id[a]]++,c[id[a]+ssize[a]]--;
        }
        vec[a].push_back(b);
        in[b]++;
    }   
    if(!slove())
    {
        for(int i = 1;i <= n;++i) printf("0\n");
    }
    else
    {
        int sum = 0;
        for(int i = 1;i <= n;++i) 
        {
            sum += c[i];
            if(sum <= 0) ans[rk[i]] = 1;
        }
        for(int i = 1;i <= n;++i) printf("%d\n",ans[i]);
    }
    system("pause");
    return 0;
}
View Code

 

上一篇:数据通信基础知识点笔记(二)


下一篇:半导体显示|LG显示器宣布在韩国投资26亿美元 生产OLED面板