思路正难则反我们定义一条路径是 “好路径”，当且仅当满足两个条件：条件 A：路径上点权的最小值 ≤ a条件 B：路径上点权的最大值 ≥ b直接求同时满足 A 和 B 的路径数比较困难。我们可以通过求它的反面来解决。根据容斥原理：满足 A 且满足 B 的路径数 = 总路径数 - 不满足 A 的路径数
展开全文
好路径的条件是“既要有小于等于 a 的点，又要有大于等于 b 的点”，那就把不好的先删掉：要么整条路都 >a，要么整条路都 <b。
所以答案=总路径数-两种坏路径，再把重复减掉的“整条路都在 (a,b) 里”加回去；而“某种条件下的路径数”在树上就是把符合条件的点分连通块，每块贡献 sz
展开全文
进行一个树形 DP记录向下路径是否包含共四种情况，DP 合并过程中统计答案
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using ll = long l
展开全文
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
using ll = long long;
class UnionFind {
public:
展开全文
容斥原理 + 并查集维护
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector&l
展开全文
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int[] fa = new int[500005];
static int[] siz =
展开全文
#include <bits/stdc++.h>
using namespace std;
struct node{
long long w,fu;
};
long long n,aa,bb;
int find(vector<struct node> &a,i
展开全文
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct UF{
UF* root;
ll rank=0;
ll cnt=1;
};
UF* Root(UF* a){
展开全文
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
#include<
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
