【p3128、LQB14I砍树】树上差分

文章目录

• 差分
• 树上差分
• p3128
• LQB14I砍树
• • 题目
  • 解题步骤
  • 代���样例

    差分

    差分数组求法：

    设原始数组是arr，差分数组是b

    • b[0] = arr[0];
    • b[i] = arr[i] - arr[i-1];

      如果我们要对图中2-4区间的数每个都加上3，就可以在差分数组2的位置加上3，在差分数组4的后一个元素即5的位置减去一个3（目的是消除3对后面区间的影响），再对差分数组前缀和即可完成。

      树上差分

      多次对树上路径做加法操作，然后询问对某个点操作后的值，适用树上差分。

      差分数组求法：

      • 叶子节点的差分值是叶子节点的权重
      • 其他节点的差分值是权-子权和
        • 权 = 差分值 + 子权和

          p3128

          LQB14I砍树

          题目

          题目信息：

          给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),

          . . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。

          小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai , bi) 满足 ai和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1.

          输入输出：

          输入共 n + m 行，第一行为两个正整数 n，m。

          后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。

          后面 m 行，每行两个正整数 ai，bi。

          一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

          输入：

          6 2

          1 2

          2 3

          4 3

          2 5

          6 5

          3 6

          4 5

          4

          输出：

          4

          解题步骤

          1. 要使砍掉一条边后每一数对都不连通，就要让所有数对都经过这条边。
          2. 将边权下移到点上，对x和y两点间的操作变为：s[x]++;s[y]++;s[LCA(x,y)]-=2;(其中s是差分数组)。
          3. 操作完成后，如果有边的权值恰好等于m，更新答案。

          代码样例

          #include using namespace std;const int N = 1e5+5;int n,m,dep[N],fa[N][21],ans,s[N];vector e[N],num[N];void dfs(int u,int father){dep[u] = dep[father] + 1;fa[u][0] = father;for(int i = 1;ifa[u][i] = fa[fa[u][i-1]][i-1];}for(int i = 0;iint v = e[u][i];if(v == father) continue;dfs(v,u);}}int LCA(int u,int v){if(dep[u] =0;i--){if(fa[u][i] != fa[v][i]) u = fa[u][i] , v=fa[v][i];}return fa[u][0];}void dfs2(int u,int Fa){for(int i = 0;iint v = e[u][i], p = num[u][i];if(v == Fa) continue;dfs2(v,u);s[u] += s[v];if(s[v] == m) ans=max(ans,p);}//if(s[u] == m) ans=max(ans,p);} int main(){cin > n >> m;for(int i = 1;iint x,y;cin > x >> y;e[x].push_back(y);e[y].push_back(x);num[x].push_back(i);num[y].push_back(i);}dfs(1,0);//差分for(int i = 1;iint a,b;cin > a >> b;s[a]++;s[b]++;s[LCA(a,b)]-=2;} //统计结果 dfs2(1,0);cout