首页 > 其他分享 >Codeforces 1044F DFS

Codeforces 1044F DFS

时间:2024-05-02 21:02:12浏览次数:21  
标签:cnt return int 1044F Codeforces DFS son maxn mx

考虑到存在方案使得以 \(u\) 为起点还能走出原树的条件。
能发现是以 \(u\) 为根,在原树上新添加的边只会是返祖边而不会有横叉边。
这是因为如果有横叉边就肯定会在遍历到一边的点后先通过这条边走到另一边的点,就算上了这条边就不是原树了。

那么考虑 \((x, y)\),合法的 \(u\) 需要满足什么条件。
首先先随意钦定一个树根,然后讨论一下 \(x, y\) 的关系:

  1. \(x, y\) 不为祖先关系。
    那么 \(x, y\) 子树内的点都是合法的。
  2. \(x, y\) 为祖先关系
    假设 \(x\) 是 \(y\) 的祖先。
    那么令 \(y'\) 为是 \(y\) 的祖先且是 \(x\) 儿子的这一个点。
    那么就有非 \(y'\) 子树内和 \(y\) 子树内的点是合法的。

考虑到这些都是子树的形式,用 \(\operatorname{dfn}\) 序来处理即可。
对于加减边,用一颗维护 \(\max\{cnt_i\}\) 和 \(\sum\limits [cnt_i = \max\{cnt_i\}]\) 的线段树即可。

时间复杂度 \(\mathcal{O}(n\log n)\)。

代码
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int n;
struct node_t {
   int mx, cnt;
   inline node_t(int mx_ = 0, int cnt_ = 0) {
      mx = mx_, cnt = cnt_;
   }
   inline node_t operator + (const node_t &o) const {
      if (mx > o.mx)
         return *this;
      if (o.mx > mx)
         return o;
      return node_t(mx, cnt + o.cnt);
   }
   inline node_t operator + (const int &x) const {
      return node_t(mx + x, cnt);
   }
   inline node_t &operator += (const int &x) {
      return *this = *this + x;
   }
};
node_t tr[maxn * 4];
int tag[maxn * 4];
inline void pushup(int k) {
   tr[k] = tr[k << 1] + tr[k << 1 | 1];
}
inline void add(int k, int x) {
   tr[k] += x, tag[k] += x;
}
inline void pushdown(int k) {
   int &v = tag[k];
   if (v) {
      add(k << 1, v), add(k << 1 | 1, v);
      v = 0;
   }
}
void build(int k = 1, int l = 1, int r = n) {
   if (l == r)
      return tr[k] = node_t(0, 1), void();
   int mid = (l + r) >> 1;
   build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
   pushup(k);
}
void update(int x, int y, int v, int k = 1, int l = 1, int r = n) {
   if (x > y)
      return ;
   if (x <= l && r <= y)
      return add(k, v), void();
   pushdown(k);
   int mid = (l + r) >> 1;
   if (x <= mid)
      update(x, y, v, k << 1, l, mid);
   if (mid < y)
      update(x, y, v, k << 1 | 1, mid + 1, r);
   pushup(k);
}
std::vector<int> son[maxn];
int dfn[maxn], dfp[maxn], rdfn[maxn], dep[maxn], siz[maxn], fa[maxn], top[maxn], dtot;
void dfs1(int u) {
   dep[u] = dep[fa[u]] + 1;
   siz[u] = 1;
   for (int &v : son[u]) {
      son[v].erase(std::find(son[v].begin(), son[v].end(), u)), fa[v] = u;
      dfs1(v);
      siz[u] += siz[v], siz[v] > siz[son[u][0]] && (std::swap(son[u][0], v), 1);
   }
}
void dfs2(int u) {
   dfn[u] = ++dtot, dfp[dtot] = u;
   for (int v : son[u]) {
      top[v] = v == son[u][0] ? top[u] : v;
      dfs2(v);
   }
   rdfn[u] = dtot;
}
inline int depfa(int u, int d) {
   for (; ; ) {
      if (dep[top[u]] > d)
         u = fa[top[u]];
      else
         return dfp[dfn[u] - (dep[u] - d)];
   }
   return -1;
}
inline void solve(int x, int y, int v) {
   if (x == y)
      return ;
   if (dfn[x] <= dfn[y] && dfn[y] <= rdfn[x]) {
      update(dfn[y], rdfn[y], v);
      y = depfa(y, dep[x] + 1);
      update(1, dfn[y] - 1, v), update(rdfn[y] + 1, n, v);
   } else if (dfn[y] <= dfn[x] && dfn[x] <= rdfn[y]) {
      update(dfn[x], rdfn[x], v);
      x = depfa(x, dep[y] + 1);
      update(1, dfn[x] - 1, v), update(rdfn[x] + 1, n, v);
   } else {
      update(dfn[x], rdfn[x], v), update(dfn[y], rdfn[y], v);
   }
}
int main() {
   int Q;
   scanf("%d%d", &n, &Q);
   for (int i = 1; i < n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      son[x].push_back(y), son[y].push_back(x);
   }
   dfs1(1), top[1] = 1, dfs2(1);
   build();
   std::set<std::pair<int, int> > S;
   for (int c = 0; Q--; ) {
      int x, y;
      scanf("%d%d", &x, &y);
      if (x > y)
         std::swap(x, y);
      std::set<std::pair<int, int> >::iterator it = S.find(std::make_pair(x, y));
      if (it == S.end())
         S.emplace(x, y), solve(x, y, 1), c++;
      else
         S.erase(it), solve(x, y, -1), c--;
      printf("%d\n", tr[1].cnt * (tr[1].mx == c));
   }
   return 0;
}

标签:cnt,return,int,1044F,Codeforces,DFS,son,maxn,mx
From: https://www.cnblogs.com/rizynvu/p/18170550

相关文章

  • Educational Codeforces Round 165 (Rated for Div. 2) C. Minimizing the Sum题解
    题意CodeforcesRound809(Div.2)D1.ChoppingCarrots(EasyVersion)给你两个整数\(n(1\len\le3e5),k(0\lek\le10)\),一个数组\(a(1\lea_i\le10^9)\)。你可以进行如下操作最多\(k\)次:选定一个数\(i(1\lei\len)\),让其变为相邻的数(变为\(a_{i-1},a_{i......
  • Codeforces Round 942 (Div. 2) (A - E)
    A.ContestProposal如果\(a_i>b_i\),则答案加一,令\(\foralli\in[i+1,n],\a_i\leftarrowa_{i-1}\)。submissionB.CoinGames题意:\(n\)枚硬币围成一圈,给出初始硬币状态,每取出一枚正面朝上的硬币并翻转相邻的两枚,没有正面则对方获胜,问先手胜负。令当前正面硬......
  • Codeforces Round 942 (Div. 2)
    CodeforcesRound942(Div.2)A.ContestProposal题意:有n个题目,每个题目的难度为a[i],要求每个题目的难度不大于对应的b[i],每次可以添加一个题目并且删去最难的题目,求最多能添加几个题目思路:暴力枚举即可,只要a[i]大于b[i],就把a[n]改为b[i],然后重新排序voidsolve(){int......
  • Codeforces Round 942 Div.2 题解
    蹭个热度,挽救一下cnblogs蒸蒸日上的阅读量。Q:你是手速狗吗?A:我觉得我是。2A因为选的\(w\)一定可以让它合法,一次操作可以看作\(a\)数组向右平移一位。枚举操作次数后暴力判断即可。#include<bits/stdc++.h>voidwork(){ intn; std::cin>>n; std::vector<......
  • Educational Codeforces Round 165 (Rated for Div. 2) 题解
    A对于\(i\top_i\)连边。如果存在二元环,则答案为2。否则答案为3。B非降序排序:0全部在1前面。令0的个数为z。从左往右,将前z个全部填上0。填第\(i\)位时,每次填的最小代价为:若第\(i\)位为1,第\(i\)位右边的第一个0到\(i\)之间的字符个数。(贪心)......
  • Codeforces Round 921 (Div. 1)
    CF1924A签到题CF1924B用set记录每个关键点的位置,每次操作带来的影响可以转化为区间加和区间乘。结果在longlong范围内但过程中可能会超。比较tricky的做法是找一个大于ans的大质数p。在\(GF(p)\)上计算。非常坏卡常CF1924C小学奥数,注意到每次折叠产生的两种折痕长度相等。前......
  • Educational Codeforces Round 164 (Div. 2)
    A-PaintingtheRibbon难度:⭐⭐解题思路先看特殊情况,如果m为1肯定不行,n小于等于k也不行;我们可以换位思考,如果Alice用了x种颜色,Bob想把其染为同一种颜色,肯定要先找出这x种颜色中染色区域最多的那一种,然后把其他区域的颜色换成该颜色,这样才是最优策略,所......
  • Educational Codeforces Round 164
    A-C简单数学题先跳过了,E题水平有限,暂时写不出来下面是D的题意ColoredBall(https://codeforces.com/contest/1954/problem/D)看题目,对于初学者来说,可能不知道使用DP怎么联想到DP的可能还是经验问题下面是个人对题目的拙见题目要求所有幂集组合里需要至少需要多少个二元对才......
  • Codeforces Round 941 (Div. 1) 题解(A-C)
    比赛链接:https://codeforces.com/contest/1965官解链接:https://codeforces.com/blog/entry/128914比较手速的一场,C与D之间出现了较大的gifficultygap。所幸C题猜得比较快(虽然证明其实比较难),最终rank190,performance2525,成功压线拿下Grandmaster。cpchenpi,堂堂上红!......
  • Codeforces Round 941 (Div. 2)
    A.CardExchange贪心。如果有某个数出现\(k\)次及以上,则通过操作使其数量变为\(k\),再变为其他出现过的数,则会增加至至少\(k\)个,一直进行如上操作,可以发现数组最终只剩\(k-1\)个数;否则为\(n\)。#include<bits/stdc++.h>usingnamespacestd;#definecctieios::......