The 2019 ACM-ICPC China Shannxi Provincial Programming Contest

A - Tasks

dp或者贪心

#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
vector v ;
int n , m , a[N] , dp[N] ;
int work()
{
  cin >> n >> m ;
  for(int i = 1; i <= n ;i ++ ) cin >> a[i] ;
  sort(a + 1 , a + n + 1) ;
  int ans = 0 ;
  for(int i = 1; i <= n ;i ++ ) {
    for(int j = m ;j >= a[i] ;j -- ) 
       dp[j] = max(dp[j] , dp[j - a[i]] + 1) , ans = max(ans , dp[j]);
  }
  cout << ans << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*

*/

B - Product

杜教筛

\[\prod_{i = 1}^{n}\prod_{j = 1}^{n}\prod_{k = 1}^{n} m^{gcd(i , j) [k |gcd(i , j)]} \% p \]

先欧拉降幂

\[= m ^ {\sum_{i = 1} ^{n}\sum_{j = 1} ^{n}\sum_{k = 1} ^{n}gcd(i , j) [k |gcd(i , j)] \% (p - 1)} \% p \]

只要求指数，然后快速幂即可

\[\sum_{i = 1} ^{n}\sum_{j = 1} ^{n}\sum_{k = 1} ^{n}gcd(i , j) [k |gcd(i , j)] \% (p - 1) \]

看式子意思是只要k是gcd(i , j)的因子，gcd(i , j) 就有一次贡献，枚举gcd(i , j) , 设d[p] 是 p因子的个数

\[\sum_{p = 1}^{n} p * d[p] \sum_{i = 1}^{n} \sum_{j = 1}^{n}[gcd(i , j) == p] \\=\sum_{p = 1}^{n} p * d[p] \sum_{i = 1}^{\frac{n}{p}} \sum_{j = 1}^{\frac{n}{p}}[gcd(i , j) == 1] \]

\[F(n) =\sum_{i = 1}^{\frac{n}{p}} \sum_{j = 1}^{\frac{n}{p}}[gcd(i , j) == 1] \\=>2\sum_{i = 1}^{n}\phi(i) - 1 \\ S(n) = \sum_{i = 1}^{n}\phi(i) \\ F(n) = 2 * S(n) - 1 \\ 原式=\sum_{p = 1}^{n} p * d[p] * F(\frac{n}{p}) \]

求S(n) , 经典杜教筛

\[S(n) = \sum_{i = 1}^{n}f(i) \\ f(i) = \phi(i) \]

迪利克雷卷积前缀和,将f乘一个积性函数g

\[S(n) = \sum_{i = 1}^{n} g * f(i) \\= \sum_{i = 1}^{n} \sum_{d|i} g(d) * f(\frac{i}{d})\\= \sum_{d = 1}^{n}g(d) * \sum_{d|i}f(\frac{i}{d})\\= \sum_{d=1}^{n}g(d) * \sum_{i = 1}^{\frac{n}{d}}f(i)\\= \sum_{d=1}^{n}g(d) * S(\frac{n}{d}) \]

进行一下充斥

\[g(1) S(n) = \sum_{d=1}^{n}g(d) * S(\frac{n}{d}) - \sum_{d=2}^{n}g(d) * S(\frac{n}{d})\\= g(1)S(n) =\sum_{i = 1}^{n} g * f(i)- \sum_{d=2}^{n}g(d) * S(\frac{n}{d})\\= g(1)S(n) =\sum_{i = 1}^{n} g * f(i)- \sum_{d=2}^{n}g(d) * S(\frac{n}{d})\\= \sum_{i = 1}^{n} \sum_{d|i} g(d) * f(\frac{i}{d})-\sum_{d=2}^{n}g(d) * S(\frac{n}{d}) \]

\[\sum_{d|i} g(d) * f(\frac{i}{d}) = \sum_{d|i} g(d) * \phi(\frac{i}{d}) \\ \sum_{d|n}\phi(\frac{n}{d}) = n\\ \]

取g函数为积性函数I(i) = 1 , 恒为1

\[\sum_{d|i} g(d) * f(\frac{i}{d}) \\= \sum_{d|i} I(d) * \phi(\frac{i}{d}) \\= i\\ g(1) S(n) =\sum_{i = 1}^{n} \sum_{d|i} g(d) * f(\frac{i}{d})-\sum_{d=2}^{n}g(d) * S(\frac{n}{d})\\ S(n) = \sum_{i = 1}^{n} i -\sum_{d=2}^{n}g(d) * S(\frac{n}{d})\\ S(n)=\frac{n * (n + 1)}{2} - \sum_{d=2}^{n}S(\frac{n}{d}) \]

\[原式=\sum_{p = 1}^{n} p * d[p] * F(\frac{n}{p}) \\F(n) = 2 * S(n) - 1 \]

最后如何求解

\[\sum_{p = 1}^{n} p * d[p] , d[p] 是p的因子个数 \\ \sum_{p = 1}^{n}\sum_{d|p}p \\=\sum_{d=1}^{n}d \sum_{p=1}^{\frac{n}{d}}p\\=\sum_{d=1}^{n}d*\frac{(1+\frac{n}{d})*\frac{n}{d}}{2} \]

\[原式=\sum_{p = 1}^n p*\frac{(1+\frac{n}{p})*\frac{n}{p}}{2} * (2S(\frac{n}{p}) - 1) \\S(n) = \sum_{i = 1} ^ n \phi(i) \]

直接对结果进行分块处理就好了。

#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
ll n , m , p ;
int phi[N] , s[N] , prime[N] , vis[N] , tot , d[N] ;
ll qmi(ll a , ll b , ll mod) {
	ll res = 1 ;
	while(b) {
		if(b & 1) res = res * a % mod ;
		b >>= 1 ;
		a = a * a % mod ;
	}
	return res ;
}
map mp ;
int Mod(ll n , int mod) {
	return (n % mod + mod) % mod ;
}
int calc_S(int n , int mod) {
	if(n < N) return s[n] ;
	if(mp.count(n)) return mp[n] ;
	int ans = Mod(1ll * n * (n + 1) / 2 , mod);
	for(int l = 2 , r ;l <= n ;l = r + 1) {
		r = n / (n / l) ;
		ans = Mod((ans - 1ll * (r - l + 1) % mod * calc_S(n / l , mod ) % mod) % mod , mod)  ;
	}
	return mp[n] = ans ;
}
ll calc_d(int n , int mod) {
	if(n < N) return d[n] ;
	int ans = 0 ;
	for(int l = 1 , r ; l <= n ; l = r + 1) {
		r = n / (n / l) ;
		int sum = ( 1ll * (r - l + 1) * (r + l) / 2 ) % mod ;
		int pre = ( 1ll * (1 + n / l) * (n / l) / 2 ) % mod  ;
		ans = Mod( ans + 1ll * sum * pre % mod , mod ) ;
	}
	return ans ;
}
void get_phi(int mod) {
	phi[1] = 1 ;
	for(int i = 2; i < N ; i ++ ) {
		if(!vis[i]) prime[++ tot] = i , phi[i] = i - 1 ;
		for(int j = 1 ; j <= tot && i * prime[j] < N ;j ++ ) {
			vis[i * prime[j]] = 1 ;
			if(i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j] ;
				break ;
			}
			phi[i * prime[j]] = phi[i] * phi[prime[j]] ;
		}
	}
	for(int i = 1; i < N ;i ++ ) 
		for(int j = i ;j < N ;j += i ) 
			 d[j] ++ ;
	for(int i = 1; i < N ;i ++ ) {
		d[i] = (d[i - 1] + 1ll * i * d[i] % mod) % mod ;
		s[i] = (s[i - 1] + phi[i] % mod) % mod ;
	}
}
int work()
{
  cin >> n >> m >> p ;
  get_phi(p - 1) ;
  if(m % p == 0) return puts("0") , 0 ;
  ll ans = 0 ;
  for(int l = 1 , r ; l <= n ; l = r + 1) {
  	r = n / (n / l) ;
  	int dn = Mod(calc_d(r , p - 1) - calc_d(l - 1 , p - 1) , p - 1) ;
  	int sn = Mod(2ll * calc_S(n / l , p - 1) - 1, p - 1)  ;
  	ans = Mod(ans + 1ll * dn * sn , p - 1) ;
  }
  cout << qmi(m , ans , p) << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*

*/

C - Angel's Journey

计算几何

先将b点变换到a的右边，根据中点对称

其中这种情况，b在c的右边最小为len(b , c) + (弧长)ac = len(b , c) + pi/2 * r

然后就是这种情况

最短为弧ac + 弧ce + len(b , e)

len(b , e)直接勾股定理

弧ac r * pi / 2

弧ce ， 先根据a4求出a1 , 在直角三角形内求出a2,然后求出a3 r * a3

vector v ;
int n , m ;
PII a , b ;
int r ;
double sq(int x) {
	return 1.0 * x * x ;
}
double len(PII a , PII b) {
	return sqrt(sq(a.x - b.x) + sq(a.y - b.y)) ;
}
PII operator - (const PII &a , const PII &b) {
	return {b.x - a.x , b.y - a.y} ;
}
double operator * (const PII &a , const PII &b) {
	return a.x * b.x + a.y * b.y ;
}
double get(PII a , PII b) {
	return acos(a * b / len(a , {0 , 0})) ;
}
int work()
{
	cin >> a.x >> a.y >> r >> b.x >> b.y ;
	PII c = {a.x + r , a.y} ;
	if(b.x <= a.x) b.x = 2 * a.x - b.x ;
	double ans = pi / 2.0 * r ;
	if(b.x >= c.x) ans += len(b , c) ;
	else {
		double ab = len(a , b) ;
		ans += sqrt(ab * ab - 1.0 * r * r) ;
		ans += 1.0 * r * ( pi / 2 - acos(1.0 * r / ab) - get(b - a , {0 , -1})) ;
	}
	printf("%.4lf\n" , ans) ;
	return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
  int n ;
  cin >> n ;
  while(n -- )
  work() ;
  return 0 ;
}
/*

*/

D - Miku and Generals

首先构造图之后发现某些点是独立点，某些点在二分图内。先处理一边二分图，然后写成两个属性值{a , b} , 选手要么选a，要么选b

对于独立点也是{a , a} ,

然后直接写个二维01背包

dp[j][2] 表示选择第n个的第几个属性能否组成j这个数值
  转移：
    dp[j][0] |= dp[j - a[i]][0]
    dp[j][0] |= dp[j - a[i]][1]
    dp[j][1] |= dp[j - a[i]][0]
    dp[j][1] |= dp[j - a[i]][1]

int a[N] , n , m , vis[N] ;
PII b[N] ;
vector v[N] ;
int dp[N][2] , sum = 0 , res = 0 ;
void dfs(int u , int f , int p) {
	vis[u] = p ;
	sum += a[u] ;
	res += p * a[u] ;
	for(auto x : v[u]) {
		if(x == f || vis[x] != -1) continue ;
		dfs(x , u , p ^ 1) ;
	}
}
int work()
{
  cin >> n >> m ;
  ll ans = 0 ;
  for(int i = 1; i <= n ;i ++ ) 
  	 cin >> a[i] , a[i] /= 100 , v[i].clear() , vis[i] = -1 , ans += a[i]  ;
  for(int i = 1; i <= m ;i ++ ) {
  	int x , y ;
  	cin >> x >> y ;
  	v[x].pb(y) , v[y].pb(x) ;
  }
  int cnt = 0 ;
  for(int i = 1; i <= n ;i ++ ) {
  	if(vis[i] != -1) continue ;
  	if(v[i].size() == 0) ++ cnt ,  b[cnt].x = b[cnt].y = a[i] , vis[i] = 2 ;
  	else sum = 0 , res = 0 , dfs(i , 0 , 0) , ++ cnt , b[cnt].x = res , b[cnt].y = sum - res ; 
  }
  for(int i = 1 ;i <= ans ;i ++ ) dp[i][0] = dp[i][1] = 0 ;
  dp[0][0] = dp[0][1] = 1 ;
  for(int i = 1; i <= cnt ;i ++ ) {
  	for(int j = ans ;j >= min(b[i].x , b[i].y) ;j -- ) {
  		if(j >= b[i].x)
	  		dp[j][0] |= dp[j - b[i].x][0] ,
	  	  	dp[j][1] |= dp[j - b[i].x][1] ;
  	  	if(j >= b[i].y)
	  		dp[j][0] |= dp[j - b[i].y][0] ,
	  		dp[j][1] |= dp[j - b[i].y][1] ;
  	}
  }
  for(int i = (ans + 1) / 2 ; i <= ans ; i ++ ) 
  	 if(dp[i][0] || dp[i][1]) {
  	 	cout << i * 100 << "\n" ;
  	 	return 0 ;
  	 }
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
  int n ;
  cin >> n ;
  while(n -- )
  work() ;
  return 0 ;
}
/*

*/

E - Tree

一看在树上对某个路径操作，并且操作频繁：树链剖分

最终判断输赢，根据nim定理，如果所有值异或为0，则先手必输

求路径异或和。

对于 | 操作，发现对于每一位来说，，如果是0，不变，如果是1，那么路径上的所有的点权的当前位都被置为1

对于 & 操作，发现对于每一位来说，，如果是1，不变，如果是0，那么路径上的所有的点权的当前位都被置为0

那么直接对每一位建立一个线段树，维护区间变为1，变为0.求区间和。

最后查询的时候对每一位进行查询，如果是奇数就加上(1 << i) ，最后再异或t。

const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 4e5 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int a[N] , son[N] , top[N] , id[N] , rk[N] , dep[N] , fa[N] , idx , sz[N] ;
vector v[N] ;
struct node {
	int sum[N] , lazy[N] ;
	void build(int rt , int l , int r , int t) {
		lazy[rt] = -1 ;
		if(l == r) {
			sum[rt] = (a[rk[l]] >> t & 1) ;
			return ;
		}
		int mid = l + r >> 1 ;
		build(ls , l , mid , t) ;
		build(rs , mid + 1 , r , t) ;
		sum[rt] = sum[ls] + sum[rs] ;
	}
	void down(int rt , int l , int r) {
		if(lazy[rt] != -1) {
			lazy[ls] = lazy[rs] = lazy[rt] ;
			int mid = l + r >> 1 ;
			sum[ls] = (mid - l + 1) * lazy[rt] ;
			sum[rs] = (r - mid) * lazy[rt] ;
			lazy[rt] = -1 ;
		}
	}
	void update(int rt , int l , int r , int ql , int qr , int k) {
		if(ql <= l && r <= qr) {
			lazy[rt] = k ;
			sum[rt] = (r - l + 1) * k ;
			// down(rt , l , r) ;
			return ;
		}
		down(rt , l , r) ;
		int mid = l + r >> 1 ;
		if(ql <= mid) update(ls , l , mid , ql , qr , k) ;
		if(qr > mid) update(rs , mid + 1 , r , ql , qr , k) ;
		sum[rt] = sum[ls] + sum[rs] ;
	}
	int ask(int rt , int l , int r , int ql , int qr ) {
		if(ql <= l && r <= qr) return sum[rt] ;
		down(rt , l , r) ;
		int mid = l + r >> 1 , ans = 0 ;
		if(ql <= mid) ans += ask(ls , l , mid , ql , qr) ;
		if(qr > mid) ans += ask(rs , mid + 1 , r , ql , qr) ;
		return ans ;
	}
}T[31] ;
void dfs1(int u , int f) {
	dep[u] = dep[f] + 1 ;
	sz[u] = 1 ;
	fa[u] = f ;
	for(auto x : v[u])  {
		if(x == f) continue ;
		dfs1(x , u) ;
		sz[u] += sz[x] ;
		if(sz[son[u]] < sz[x]) son[u] = x ;
	}
}
void dfs2(int u , int t) {
	top[u] = t ;
	id[u] = ++ idx ;
	// cout << u << " " << id[u] << " ---- " << top[u] << "\n" ;
	rk[idx] = u ;
	if(son[u]) dfs2(son[u] , t) ;
	for(auto x : v[u]) {
		if(x == fa[u] || x == son[u]) continue ;
		dfs2(x , x) ;
	}
}
int work()
{
  int n ,  q ;
  cin >> n >> q ;
  for(int i = 1; i <= n ;i ++ ) cin >> a[i] ;
  	// puts("S") ;
  for(int i = 1; i < n ;i ++ ) {
  	int x , y ;
  	cin >> x >> y ;
  	v[x].pb(y) , v[y].pb(x) ;
  }
  dfs1(1 , 0) ;
  dfs2(1 , 1) ;
  for(int i = 0 ;i < 31;i ++ )  
  	 T[i].build(1 , 1 , n , i) ;
  while(q -- ) {
  	int op , s , t ;
  	cin >> op >> s >> t; 
  	if(op == 1) {
  		while(s) {
  			for(int i = 0 ;i < 31; i ++ ) 
  				 if(t >> i & 1) 
  				 	T[i].update(1 , 1 , n , id[top[s]] , id[s] , 1) ;
  			s = fa[top[s]] ;
  		}
  	}else if(op == 2){
  		while(s) {
  			for(int i = 0 ;i < 31; i ++ )
  				 if((t >> i & 1) == 0)
  				 	 T[i].update(1 , 1 , n , id[top[s]] , id[s] , 0)  ; // , cout << i << " " << id[top[s]] << " +++ " << id[s] << "\n";
  			s = fa[top[s]] ;
  		}
  	}else if(op == 3){
  		int res = 0 ;
  		while(s) {
  			for(int i = 0 ;i < 31 ;i ++ ){
  				// cout << i << " " << id[top[s]] << " " << id[s] << " " << T[i].ask(1 , 1 , n , id[top[s]] , id[s]) << "\n" ;
  				res ^= (1 << i) * (T[i].ask(1 , 1 , n , id[top[s]] , id[s]) % 2) ;
  			}
  			s = fa[top[s]] ;
  		}
  		// cout << res << "\n" ;
  		if(res == t) puts("NO") ;
  		else puts("YES") ;
  	}else {
  		for(int i = 0 ;i < 5; i ++ ) {
  			cout << i << " " << T[i].ask(1 , 1 , n , s , t) << "\n" ;
  		}
  	}
  }
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
12 13
2 1 2 1 2 1 2 1 2 1 2 1
1 2
1 3
2 4
2 5
4 8
5 9 
5 10
3 6
3 7
6 11
7 12
2 12 4
3 6 1
1 10 2
2 7 2
3 6 1
3 1 1
2 6 1
3 11 2
*/

J - And And And

只需要统计有多少路径异或位0，然后加上两端点分别向两边延申的个数相乘

最关键的是怎么算贡献

点分治

对于每个重心节点，他的所有子树可能存在一个链向上

比如重心节点2，那么此时对于1来说，和其他节点组合的贡献值是多少呢。 答案是1

这里怎么求解的方法是个小技巧，

对于重心节点向下的分支，他们的大小就是sz[u] , 但是存在一段从重心节点一直往上

只需要在刚开始做遍遍历，求出每个节点的父亲节点。

然后在对每个重心节点进行遍历子树的时候再进行求一次父亲节点，如果相同，就说明他是从上向下的，否则就是从下到上的。

如果是从下到上的，那么他的延申节点就是n - sz[fa[u]] ，否则的话就是sz[u]

然后难点基本就没有了。

const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
vector v[N] ;
int n , m , sz[N] , vis[N] ;
int rt , sum , res ;
int get_rt(int u , int f) {
	sz[u] = 1 ; 
	int maxn = 0 ;
	for(auto x : v[u]) {
		if(x.x == f || vis[x.x]) continue ;
		get_rt(x.x , u) ; 
		sz[u] += sz[x.x] ;
		maxn = max(maxn , sz[x.x]) ;
	}
	maxn = max(maxn , sum - sz[u]) ;
	if(maxn < res) res = maxn , rt = u ;
}
int dep[N] , fa[N], s[N] ;
void dfs(int u , int f) {
	s[u] = 1 ;
	fa[u] = f ;
	for(auto x : v[u]) {
		if(x.x == f) continue ;
		dfs(x.x , u) ;
		s[u] += s[x.x] ;
	}
}
ll ans = 0 ;
unordered_map mp , c;
int ff[N] ;
void get_xor(int u , int f , ll w) {
	ff[u] = f ;
	if(f) c[u] = w ;
	for(auto x : v[u]) {
		if(x.x == f || vis[x.x]) continue ;
		get_xor(x.x , u , w ^ x.y) ;
	}
}
ll get_sz(int x) {
	if(ff[x] == fa[x]) return s[x] ;
	return (n - s[ff[x]]) ;
}
ll get(int x , int y) {
	return 1ll * get_sz(x) * get_sz(y) % mod ;
}
void calc(int u) {
	mp.clear() ;
	for(auto x : v[u]) {
		if(vis[x.x]) continue ;
		c.clear() ;
		get_xor(x.x , u , x.y) ;
		int y = x.x ;
		for(auto z : c) {
			if(z.y == 0) {
				if(fa[y] == u) ans = (ans + get_sz(z.x) * (n - s[y]) % mod) % mod ; 
				else ans = (ans + get_sz(z.x) * s[u] % mod) % mod ; 
			}
			ans = (ans + mp[z.y] * get_sz(z.x) % mod) % mod ;
		}
		for(auto z : c) 
			mp[z.y] = (mp[z.y] + get_sz(z.x)) % mod ; 
		
	}
}
void solve(int u) {
	vis[u] = 1 ;
	calc(u) ;
	for(auto x : v[u]) {
		if(vis[x.x]) continue ;
		sum = res = sz[x.x] ;
		get_rt(x.x , u) ;
		solve(rt) ;
	}
}
int work()
{
	cin >> n ;
	for(int i = 2; i <= n ;i ++ ) {
		int x ;
		ll w ;
		cin >> x >> w ;
		v[i].emplace_back(x , w) ;
		v[x].emplace_back(i , w) ;
	}
	dfs(1 , 0) ;
	sum = res = n ;
	get_rt(1 , 0) ;
	solve(rt) ;

	cout << ans << "\n" ;
	return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
16
1 2
2 2
3 1
2 1
5 1
5 2
5 4
2 3
9 3
9 1
1 1
12 3
12 2
13 1
13 2

8
1 2
2 2
3 1
2 1
5 1
5 2
5 4
*/

dfs搜索

先对整个树进行一个异或，dis[i] , 表示从根节点到i节点的异或和

那么对于任意两个相同值dis的节点,即符合题目要求。

遍历整个树，遍历到当前节点的时候，

需要查找一下当前节点所有的祖先节点的值是否有相同的。

还需要查找一下之前已经访问过的分支的dis值时候又相同的。

访问完当前分支需要回溯，将当前点对其子树节点的贡献剪掉

vector v[N] ;
unordered_map mp ;
ll dis[N] ;
ll ans = 0 ;
void dfs(int u , int f) {
	sz[u] = 1 ;
	for(auto x : v[u]) {
		if(x.x == f) continue ;
		dis[x.x] = dis[u] ^ x.y ;
		dfs(x.x , u) ;
		sz[u] += sz[x.x] ;
	}
}
ll Mod(ll x) {
	return (x % mod + mod) % mod ;
}
void dfs_calc(int u , int f) {
//当前节点的总贡献
	ans = Mod(ans + 1ll * sz[u] * mp[dis[u]] % mod) ;
	for(auto x : v[u]) {
		if(x.x == f) continue ;
		//当前节点对孩子节点的贡献
		mp[dis[u]] = Mod(mp[dis[u]] + 1ll * n - sz[x.x]);
		dfs_calc(x.x , u) ;
		// 回溯
		mp[dis[u]] = Mod(mp[dis[u]] - 1ll * n + sz[x.x]);
	}
	// 当前分支对后面未访问分支的贡献
	mp[dis[u]] = Mod(mp[dis[u]] + sz[u]) ;
}
int work()
{
  cin >> n ;
  for(int i = 2; i <= n ;i ++ ) {
  	int x ;
  	ll y ;
  	cin >> x >> y ;
  	v[x].emplace_back(i , y) ;
  }
  dfs(1 , 0) ;
  dfs_calc(1 , 0) ;
  cout << ans << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*

*/

L - Swap

打表找规律

M - Travel

二分+01bfs，因为每增加一次的代价、扩张都是一样的。

只需要二分一下扩展mid次，然后对于w[i] <= mid * d的边贡献都是1，否则都是0

最后只需要判断一下最短路是否是mid * e

vector v[N] ;
bool check(ll d , ll e) {
	vector dis(n + 1) ;
	vector vis(n + 1) ;
	for(int i = 1; i <= n ;i ++ ) dis[i] = INF , vis[i] = 0 ;
	dis[1] = 0 ;
	priority_queue , greater > q ;
	q.push({0 , 1}) ;
	while(q.size()) {
		int u = q.top().y ;
		q.pop() ;
		if(u == n) {
			// cout << d << " " << e << " " << dis[u] << "\n" ;
			return dis[u] <= e ;
		}
		if(vis[u]) continue ;
		vis[u] = 1 ;
		for(auto x : v[u]) {
			if(x.y > d) continue ;
			if(dis[x.x] > dis[u] + 1) {
				dis[x.x] = dis[u] + 1 ;
				if(dis[x.x] > e) continue ;
				q.push({dis[x.x] , x.x}) ;
			}
		}
	}
	return dis[n] <= e ;
}
int work()
{
  cin >> n >> m >> c >> d >> e ;
  for(int i = 1; i <= m ;i ++ ) {
  	int a , b , w ;
  	cin >> a >> b >> w ;
  	v[a].emplace_back(b , w) ;
  	v[b].emplace_back(a , w) ;
  }
  int l = 0 , r = INF , ans = 0 ;
  while(l <= r) {
  	int mid = l + r >> 1 ;
  	if(check(1ll * mid * d , 1ll * mid * e)) r = mid - 1 , ans = mid ;
  	else l = mid + 1 ;
  }
  // cout << ans << "\n" ;
  if(ans)
  	cout << 1ll * ans * c << "\n" ;
  else puts("-1") ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*

*/
ICPC区域赛

相关

标签