https://www.zybuluo.com/ysner/note/1311166

題面

有一棵大小為\(n\)的帶邊權、點權的樹，問有多少點對\((i,j)(i<j)\)滿足：
點權異或和\(>\)樹上簡單路徑的最大邊權。

• \(n\leq2*10^5\)

  解析

  這個最大邊權顯然不是暴力求出來的，因為要求給出兩個點，復雜度\(O(n^2)\)。
  所以我們要枚舉邊權。

一開始可能會想到，從最大邊開始，統計其兩端子樹之間的貢獻，然后分治搞下去。
但這樣其實很難保證復雜度。
換個方向思考，可以像做最小生成樹一樣，從小往大加邊。
顯然每加一條邊，這條邊就是兩端聯通塊相互之間的最大邊權。

然后異或和顯然可以弄棵\(Trie\)樹來搞。
這個\(Tire\)樹可以跟著并查集一起維護，每次合并并查集的同時把\(Trie\)樹也合并。
所以需要線段樹合并\(or\)可持久化\(Trie\)。
（注意如果一個一個點地合并\(Trie\)樹會\(TLE\)!!!)

最后注意邊界，\(Insert\)到\(d<0\)時，新建結點再\(return\)；而\(Query\)直接\(return\)。

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define re register #define il inline #define fp(i,a,b) for(re int i=a;i<=b;++i) #define fq(i,a,b) for(re int i=a;i>=b;--i) using namespace std; const int N=2e5+100; int n,val[N],W,h[N],cnt,sz[N*32],da[N],t[2][N*32],f[N],rt[N],sta[N*32],top; ll ans; struct dat{int u,v,w;il bool operator < (const dat &o) const {return w<o.w;}}a[N]; struct Edge{int to,nxt;}e[N<<1]; il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;} il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);} il ll gi() {re ll x=0,t=1;re char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t; } il void Insert(re int &x,re int k,re int d) {if(!x) x=sta[top--];++sz[x];if(d<0) return;Insert(t[(k>>d)&1][x],k,d-1); } il int Query(re int x,re int k,re int w,re int d) {if(d<0) return 0;re int A=k>>d&1,B=w>>d&1,s=0;if(!B) s+=sz[t[A^1][x]];s+=Query(t[A^B][x],k,w,d-1);return s; } il void dfs1(re int u,re int fa,re int x,re int w) {ans+=Query(rt[x],val[u],w,29);for(re int i=h[u];i+1;i=e[i].nxt){re int v=e[i].to;if(v==fa) continue;dfs1(v,u,x,w);} } il void clear(re int x) {if(!x) return;clear(t[0][x]);clear(t[1][x]);t[0][x]=t[1][x]=sz[x]=0;sta[++top]=x; } il int Merge(re int x,re int y) {if(x) sz[x]+=sz[y];if(!x||!y) return x+y;t[0][x]=Merge(t[0][x],t[0][y]);t[1][x]=Merge(t[1][x],t[1][y]);return x; } int main() {memset(h,-1,sizeof(h));fq(i,2e5*32,1) sta[++top]=i;n=gi();fp(i,1,n) val[i]=gi(),f[i]=i,da[i]=1,Insert(rt[i],val[i],29);fp(i,1,n-1) a[i].u=gi(),a[i].v=gi(),a[i].w=gi();sort(a+1,a+n);fp(i,1,n-1){re int u=find(a[i].u),v=find(a[i].v);if(da[u]<da[v]) swap(u,v);dfs1(v,0,u,a[i].w);Merge(rt[u],rt[v]);f[v]=u;da[u]+=da[v];add(u,v);}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/yanshannan/p/9794294.html

總結

以上是生活随笔為你收集整理的一道不知名的题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。