【模板】字典树 3

Jair314 LV 5 @ 2021-11-4 17:27:33

从洛谷 P4551 最长异或路径过来的

通过那个题的结论我们可以知道 $dist(x,y)=dist(x,rt)$ ^ $dist(rt,y)$

首先可以对问题化简，我们先来看一个题

给定序列 A，求 $i < j$ 且 $A_i < A_j$ 的个数

按照 $j \in [1,n]$ 的顺序扫一遍，每次先查询当前 trie 中与 $val_j$

异或结果 $>= k$ 的数量（直接 trie 上二分贪心即可），

然后把 $val_j$ 加入 trie 中

那么这个题，我们可以 dfs 预处理出 $dist(rt,u) ( u∈[1,n] )$

然后问题就转化成了上面那个问题

$Talking \; is \; cheap , \; show \; the \; code.$

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

#define int long long

/***** Fast_IO *****/

using std::cin;
using std::cout;
using vii = std::vector<int> ;
using pii = std::pair<int,int> ;

namespace IO{
	char buf[(1<<21)],*p1=buf,*p2=buf,buf1[(1<<21)]; int _=0;

	inline char gc (){
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<21),stdin),p1==p2)?EOF:*p1++;
	}

	#define gc getchar
	#define pc putchar
	#define ONLINE_JUDGE OJ

	template<class I>
	inline I read(I &x){
		x=0; I f=1; char c=gc(); if(c==EOF){ return -1; }
		while(c<'0'||c>'9'){ if(c=='-'){ f=f*(-1); } c=gc(); }
		while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
		return x=x*f;
	}

	template<typename I,typename ...Args>
	inline void read(I &a, Args &...args){
		read(a),read(args...);
	}

	template<class I>
	inline void write(I x){
		if(x==0){ pc('0'); return; }
		int tmp=x>0?x:(-x),cnt=0;
		if(x<0){ pc('-'); }
		while(tmp){ buf[cnt++]=(tmp%10)+'0'; tmp/=10; }
		while(cnt){ pc(buf[--cnt]); }
		return;
	}

	void _FILE(){
		#ifndef ONLINE_JUDGE
			freopen("text.in","r",stdin);
			freopen("text.out","w",stdout);
		#endif
	}
	
	template<class I>
	inline void chmax(I &x,I y){ return x=max(x,y),void(); }
	
	template<class I>
	inline void chmin(I &x,I y){ return x=min(x,y),void(); }

	#define out(x) write(x),pc(' ')
	#define outn(x) write(x),pc('\n')
	#define assi() pc('\t')
	#define FOR(i,a,b) for(int i(a);i<=(b);++i)
	#define ROF(i,a,b) for(int i(a);i>=(b);--i)
	#define FORs(i,a,b,s) for(int i(a);i<=(b);i+=(s))
	#define ROFs(i,a,b,s) for(int i(a);i>=(b);i-=(s))
	#define next(i,now) for(int i(link[now]);i;i=edge[i].nexty)
	#define each(i,v) for(auto &i:v)
	#define all(v) v.begin(),v.end()
	#define sqr(k) ((k)*(k))
	#define inf 0x3f3f3f3f
	#define pb push_back
	#define mp make_pair
	#define fir first
	#define sec second
}using namespace IO;

/***** Fast_IO *****/

#define maxn 1000010
#define SIZE 5010

int n,k;

namespace GRA{
	struct Edge{ int start,end,val,nexty; }edge[(maxn)<<1];

	int link[maxn],edge_cnt;

	void add_edge(int u,int v,int w){
		edge[++edge_cnt]=(Edge){u,v,w,link[u]};
		link[u]=edge_cnt;
	}
}using namespace GRA;

int DIGIT(int S,int k){ return S>>(k-1)&1; }

class Trie{
	private:
		struct Trie_tree{ int son[2],cnt; }trie[(maxn)<<5];

		int trie_cnt=1;

	public:
		void insert(int S){
			int u=1,v=0;
			ROF(i,32,1){
				++trie[u].cnt;
				v=DIGIT(S,i);
				(!trie[u].son[v])&&
				(trie[u].son[v]=++trie_cnt);
				u=trie[u].son[v];
			}
			++trie[u].cnt;
		}

		int query(int S){
			int res=0;
			int u=1,v1=0,v2=0;
			ROF(i,32,1){
				v1=DIGIT(S,i);
				v2=DIGIT(k,i);
				// (v2==0)&&(outn(trie[trie[u].son[v1^1]].cnt));
				(v2==0)&&(res+=trie[trie[u].son[v1^1]].cnt);
				(v2==0)&&(u=trie[u].son[v1]);
				(v2==1)&&(u=trie[u].son[v1^1]);
			}
			return (res+=trie[u].cnt);
		}
}tr;

int val[maxn];

void dfs(int now,int fa){
	next(i,now){
		int ver=edge[i].end;
		if(ver==fa){ continue; }
		val[ver]=val[now]^edge[i].val;
		dfs(ver,now);
	} return;
}

signed main(){
	_FILE();
	read(n,k);
	FOR(i,1,n-1){
		int u,v,w;
		read(u,v,w);
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	dfs(1,0);
	// FOR(i,1,n){ read(val[i]); }
	int res=0;
	FOR(i,1,n){ res+=tr.query(val[i]); tr.insert(val[i]); }
	outn(res);
	return 0;
}

/*
3 2
1 2 3
*/