首页 > 代码库 > pair
pair
这个是非常经典的树分治的题目,关于60分的做法.参见poj1741
按照树分治的惯例,先全局统计,然后再减掉重复的东西.
那么如何计算贡献呢?
我们按照poj1741的方法.先将满足一维的情况的数据全部放入一个树状数组里面,然后我们就能够一维统计了.
复杂度O(nlog2n)
代码也比较凑合....
#include<cstdlib>#include<cstdio>#include<cstring>#include<algorithm>#include<deque>#ifdef WIN32#define fmt64 "%I64d"#else#define fmt64 "%lld"#endifusing namespace std;const int maxn = (int)1.5e5, inf = 0x3f3f3f3f;struct E{ int t,w,last;}e[maxn * 2];struct Q{ int w,l;}data[maxn];int cmp(Q x, Q y){ if(x.w != y.w) return x.w < y.w; return x.l < y.l;}int last[maxn],cnt;int node,tmax;int n,L,W;int size;struct BIT{ int bt[maxn]; int lowbit(int x){ return x & (-x); } void ins(int pos,int val){ while(pos <= n){ bt[pos] += val; pos += lowbit(pos); } } int qer(int pos){ int ret = 0; while(pos > 0){ ret += bt[pos]; pos -= lowbit(pos); } return ret; }}bit;void add(int x,int y,int w){ e[++cnt] = (E){y,w,last[x]}; last[x] = cnt; e[++cnt] = (E){x,w,last[y]}; last[y] = cnt;}int sz[maxn],vis[maxn];int root;void getroot(int x,int fa){ sz[x] = 0; int Max = 0; for(int i = last[x]; i; i = e[i].last) if(e[i].t != fa && !vis[e[i].t]){ getroot(e[i].t, x); Max = max(Max, sz[e[i].t] + 1); sz[x] += sz[e[i].t] + 1; } Max = max(Max, node - sz[x] - 1); if(tmax >= Max) root = x, tmax = Max;}int add1,add2;long long ans;void getdata(int x,int fa,int sumw,int suml){ int cost1 = sumw + add1, cost2 = suml + add2; if(cost1 <= W && cost2 <= L) data[++size] = (Q){cost1,cost2}; for(int i = last[x]; i; i = e[i].last) if(e[i].t != fa && !vis[e[i].t]) getdata(e[i].t, x, sumw + e[i].w, suml + 1);}long long process(){ sort(data + 1, data + size + 1, cmp); int h = 1,t = size; long long ret = 0; deque<Q>q; deque<int>qq; while(h < t || !q.empty()){ while(!q.empty() && qq.back() <= h){ bit.ins(q.back().l, -1); q.pop_back(), qq.pop_back(); } while(!q.empty() && q.front().w + data[h].w > W){ bit.ins(q.front().l, -1); q.pop_front(), qq.pop_front(); } if(data[t].w + data[h].w > W) { t--; continue; } else{ while(h < t && data[t].w + data[h].w <= W){ bit.ins(data[t].l, 1); q.push_back(data[t]); qq.push_back(t--); } ret += bit.qer(L - data[h++].l); } } return ret;}long long calc(int x,int ad1,int ad2){ size = 0; add1 = ad1; add2 = ad2; getdata(x,0,0,0); return process();}void solve(int x){ ans += calc(x, 0, 0); vis[x] = 1; for(int i = last[x]; i; i = e[i].last) if(!vis[e[i].t]){ ans -= calc(e[i].t, e[i].w, 1); node = sz[e[i].t]; tmax = inf; getroot(e[i].t, root = 0); solve(root); }}void work(){ node = n; tmax = inf; getroot(1,0); solve(root);}int main(){ freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); scanf("%d %d %d",&n,&L,&W); for(int i = 2; i <= n; ++i){ int p,w; scanf("%d %d",&p,&w); add(i,p,w); } work(); printf(fmt64"\n", ans); return 0;}
pair
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。