比赛 2024暑假C班集训E 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEEEEEEEEEEA
题目名称 部落冲突 最终得分 60
用户昵称 liuyiche 运行时间 12.402 s
代码语言 C++ 内存使用 16.15 MiB
提交时间 2024-07-14 11:46:32
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P; 

int n, m, cnt = 0;
vector<int> c(100005,0);
bool p[6005][6005];

struct node
{
    vector<int> nxt;
};
vector<node> v(300005);
vector<P> x(300005);

bool vis[6005];
int f[6005];

int Lowbit (int x)
{
    return x&(-x);
}
 
void Add (int a, int b)
{
    for (int i = a; i <= n; i+=Lowbit(i))
        c[i] += b;
}
 
int Sum (int a, int b)
{
    int suma = 0, sumb = 0;
    for (int i = a-1; i > 0; i-=Lowbit(i))
        suma += c[i];
    for (int i = b; i > 0; i-=Lowbit(i))
        sumb += c[i];
   return sumb-suma;
}

inline bool dfs(int step, int to)
{
    if(step == to)
        return true;
    if(f[step] != -1)
        return f[step];
    vis[step] = 1;
    bool ans = 0;
    for(int i = 0; i < v[step].nxt.size(); ++i)
        if(p[step][v[step].nxt[i]] == 0 && vis[v[step].nxt[i]] == 0)
            ans = max(ans,dfs(v[step].nxt[i],to));
    vis[step] = 0;
    return f[step] = ans;
}

int main()
{
    freopen("lct.in","r",stdin);
    freopen("lct.out","w",stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        v[x].nxt.push_back(y);
        v[y].nxt.push_back(x);
    }
    if(n > 6000)
    {
        for(int i = 1; i <= m; ++i)
        {
            char ch;
            cin >> ch;
            if(ch == 'Q')
            {
                int x, y;
                cin >> x >> y;
                if(x > y)
                    swap(x,y);
                if(Sum(x,y-1) == 0)
                    cout << "Yes" << '\n';
                else
                    cout << "No" << '\n';
            }
            else if(ch == 'C')
            {
                cnt++;
                cin >> x[cnt].first >> x[cnt].second;
                Add(min(x[cnt].first,x[cnt].second),1);
            }
            else
            {
                int idx;
                cin >> idx;
                Add(min(x[idx].first,x[idx].second),-1);
            }
        }
        return 0;
    }
    for(int i = 1; i <= m; ++i)
    {
        char ch;
        cin >> ch;
        if(ch == 'Q')
        {
            int x, y;
            cin >> x >> y;
            for(int i = 1; i <= n; ++i)
                f[i] = -1;
            if(dfs(x,y) == true)
                cout << "Yes" << '\n';
            else
                cout << "No" << '\n';
        }
        else if(ch == 'C')
        {
            cnt++;
            cin >> x[cnt].first >> x[cnt].second;
            p[x[cnt].first][x[cnt].second] = 1;
            p[x[cnt].second][x[cnt].first] = 1;
        }
        else
        {
            int idx;
            cin >> idx;
            p[x[idx].first][x[idx].second] = 0;
            p[x[idx].second][x[idx].first] = 0;
        }
    }
    return 0;
}