@OceanEye7年前
04/8
18:43
这题主席树的处理还是有点神的，，
maya我直接抄题解就好了，，反正我方法的和题解是一样的。
但是我比好多人都慢啊QAQ不服气
首先转化问题。两棵树的公共祖先，很扯淡。计算出每两个点的两棵树上的公共祖先我用的复杂度是n^2·logn
妈呀根本不能接受，妥妥的TLE
那么我们计算祖先的贡献怎么样？
首先假设某个点有x个公共儿子，那么他对总的亲密度的贡献是x*(x-1)/2【自己脑补组合数】
但是看一眼数据范围，首先O(n)应该是不可能的了。那么我们能不能在nlogn的时间内瞎搞出所有节点的公共儿子呢qwq
平衡树？搞毛，，线段树？搞毛，，树剖？不好意思不会，，主席树？于是又神奇的想到了转化问题
他的标号是混乱的，这很不清真，，换成DFS序怎么样？
第二棵树呢？还是混乱的，，
混乱又怎么样，，再标一次就好了。这个时候我们要的就是完成两个集合求交集的工作。
那么主席树出场了！
第一棵树的节点先按照dfs序重新编号，记节点A的子节点为l到r
然后第二棵树也这么做，，记节点A的子节点为L到R
这个时候，会惊奇发现他们的公共儿子【交集】不就是求[L,R]中有多少个元素属于[l,r]的么，，
由于这个东西目测满足区间加法，所以主席树应该是可行的。
那么就主席树瞎搞一下，，A掉。
爽！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <vector> using namespace std; const int maxn = 100050; const int NIL = 0; struct Tr { int lc,rc,cnt,l,r; }pool[maxn*20]; struct node { int num,l,r,L,R; }a[maxn]; vector <int> T[maxn]; int n,i,j,x,y,T_cnt,id[maxn],root[maxn]; bool vis[maxn]; void dfs2(int k,int &cnt) { id[cnt] = k; int cur = cnt; for(int i=0;i<T[k].size();i++) dfs2(T[k][i],++cnt); if (T[k].size() > 0) { a[k].L = cur+1; a[k].R = cnt; } T[k].clear(); } void dfs1(int k,int &cnt) { a[k].num = cnt; for(int i=0;i<T[k].size();i++) dfs1(T[k][i],++cnt); if (T[k].size() > 0) { a[k].l = a[k].num+1; a[k].r = cnt; } T[k].clear(); } void insert(int &x,int num,int l,int r) { pool[T_cnt++] = pool[x]; x = T_cnt-1; pool[x].cnt++; pool[x].l = min(pool[x].l,num); pool[x].r = max(pool[x].r,num); if (l==r) return; int mid = (l+r)>>1; if(num <= mid) insert(pool[x].lc,num,l,mid); else insert(pool[x].rc,num,mid+1,r); } int query(int i,int j,int l,int r) { if (pool[j].l > r || pool[j].r < l) return 0; if (pool[j].l >= l && pool[j].r <= r) return pool[j].cnt - pool[i].cnt; if (pool[j].l==pool[j].r) return 0; return query(pool[i].lc,pool[j].lc,l,r) + query(pool[i].rc,pool[j].rc,l,r); } int main() { scanf("%d",&n); memset(vis,false,sizeof(vis)); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); vis[y] = true; T[x].push_back(y); } for(i=1;i<=n;i++) if (!vis[i]) { int cnt = 1; dfs1(i,cnt); break; } memset(vis,false,sizeof(vis)); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); vis[y] = true; T[x].push_back(y); } for(i=1;i<=n;i++) if(!vis[i]) { int cnt = 1; dfs2(i,cnt); } T_cnt = 1; pool[0].lc = pool[0].rc = pool[0].cnt = NIL; root[NIL] = NIL; pool[0].l = maxn; pool[0].r = 0; for(i=1;i<=n;i++) { root[i] = root[i-1]; insert(root[i],a[id[i]].num,1,n); } long long ans = 0; for(i=1;i<=n;i++) { int k = query(root[a[id[i]].L-1],root[a[id[i]].R],a[id[i]].l,a[id[i]].r); ans += (1ll)*k*(k-1)/2; } printf("%lld\n",ans); return 0; } |