「POJ1741」Tree
Description
Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
|
1 2 3 4 5 6 |
5 4 1 2 3 1 3 1 1 4 2 3 5 1 0 0 |
Sample Output
|
1 |
8 |
题解
复习了一下点分治，准确的说上次学的时候根本没有学会T T
发现确实比链分治简单不少
所谓点分治 对于一条树路径 只有经过或不经过一个点的情况
对于不经过的情况 把一棵树按这个点拆成好几棵分治就行了
考虑经过这个点的情况
对于这题 可以对这个点延伸出的几棵子树各做一次dfs
记录子树中出现的距离值
对于一棵树的距离值数组
把它排序求一次ans1
再对每棵子树分别求一个自己对自己的ans2
\(ans1-\sum ans2\)即为最后的ans
也可以用平衡树来维护信息
考虑经过根的路径，依次处理其子树，维护平衡树，对于第S棵子树其每个结点x，在平衡树中查询出发点为根，终点在S-1子树中，小于K-dis[x]+1的路径数量num，ans+=num
再用S更新平衡树
1.点分治+排序
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define inf 0x7fffffff using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,cnt,sum,ans,root; int head[10005],deep[10005],d[10005],f[10005],son[10005]; bool vis[10005]; struct data{int to,next,v;}e[20005]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} void getroot(int x,int fa) { son[x]=1;f[x]=0; for(int i=head[x];i;i=e[i].next) { if(e[i].to==fa||vis[e[i].to])continue; getroot(e[i].to,x); son[x]+=son[e[i].to]; f[x]=max(f[x],son[e[i].to]); } f[x]=max(f[x],sum-son[x]); if(f[x]<f[root])root=x; } void getdeep(int x,int fa) { deep[++deep[0]]=d[x]; for(int i=head[x];i;i=e[i].next) { if(e[i].to==fa||vis[e[i].to])continue; d[e[i].to]=d[x]+e[i].v; getdeep(e[i].to,x); } } int cal(int x,int now) { d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); int t=0,l,r; for(l=1,r=deep[0];l<r;) { if(deep[l]+deep[r]<=K){t+=r-l;l++;} else r--; } return t; } void work(int x) { ans+=cal(x,0); vis[x]=1; for(int i=head[x];i;i=e[i].next) { if(vis[e[i].to])continue; ans-=cal(e[i].to,e[i].v); sum=son[e[i].to]; root=0; getroot(e[i].to,root); work(root); } } int main() { while(1) { ans=0;root=0;cnt=0; memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); n=read();K=read(); if(n==0)break; for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } sum=n;f[0]=inf; getroot(1,0); work(root); printf("%d\n",ans); } return 0; } |
2.点分治+treap
|
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include<ctime> #include<cstdio> #include<iostream> #define ll long long #define N 10005 using namespace std; ll ans,K; int n,cnt,tot,rt; int last[N],f[N],size[N],val[N]; bool vis[N]; struct edge{ int to,next,v; }e[2*N]; struct treap{ int cnt,rt; int l[N],r[N],size[N],v[N],w[N],rnd[N]; void ini(){ cnt=rt=0; } void update(int k){ size[k]=size[l[k]]+size[r[k]]+w[k]; } void rturn(int &k){ int t=l[k];l[k]=r[t];r[t]=k;update(k);update(t);k=t; } void lturn(int &k){ int t=r[k];r[k]=l[t];l[t]=k;update(k);update(t);k=t; } void insert(int &k,int val){ if(!k) { k=++cnt;rnd[k]=rand();w[k]=size[k]=1;v[k]=val; l[k]=r[k]=0; return; } size[k]++; if(val==v[k])w[k]++; else if(val<v[k]){insert(l[k],val);if(rnd[l[k]]<rnd[k])rturn(k);} else {insert(r[k],val);if(rnd[r[k]]<rnd[k])lturn(k);} } int query(int k,int val){//求小于val的元素个数 if(!k)return 0; if(v[k]==val) return size[l[k]]; else if(v[k]<val) return size[l[k]]+w[k]+query(r[k],val); else return query(l[k],val); } }treap; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void getrt(int x,int fa)//求重心 { size[x]=1;f[x]=0; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { getrt(e[i].to,x); f[x]=max(f[x],size[e[i].to]); size[x]+=size[e[i].to]; } f[x]=max(f[x],tot-size[x]); if(f[x]<f[rt])rt=x; } void getdis(int x,int fa,int flag)//加入or查询子树信息 { if(flag==0)treap.insert(treap.rt,val[x]); else ans+=treap.query(treap.rt,K-val[x]+1); for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { val[e[i].to]=val[x]+e[i].v; getdis(e[i].to,x,flag); } } void solve(int x) { vis[x]=1; treap.ini(); treap.insert(treap.rt,0); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { val[e[i].to]=e[i].v; getdis(e[i].to,x,1);//查询 getdis(e[i].to,x,0);//插入 } for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { tot=size[e[i].to];rt=0; getrt(e[i].to,x); solve(rt); } } int main() { while(scanf("%d%lld",&n,&K)) { if(n==0)break; memset(vis,0,sizeof(vis)); memset(last,0,sizeof(last)); ans=cnt=0; for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } tot=n;f[0]=n;rt=0; getrt(1,0); solve(rt); cout<<ans<<endl; } return 0; } |
计数器 9794043
OI 课件=>
OI 课件=>
黄学长QAQ 感觉您的重心找的不对啊 求轻喷
分治的时候不太对，但是我觉得实际上也没什么关系
楼下有人问了
扑通扑通跪下来，千古神犇黄哲威
学长博客前几天都打不开QAQ
请问每次getroot()以后，需不需要把原来树中root的父结点的son值更新为sum-size[root]？因为getroot()以后原树中root的父结点会变为root的子结点。
一般情况也影响不了运行时间，我测过 TAT
orz折腾了好久。。。
神犇WC考得怎么样？
RAR 和没分似的
这个可以证明的吗。。还是可以构造卡掉？我一直没想通怎么可以卡掉orz求教育
哦可以证明吧，即使能卡掉，同一棵树不同的写法也可能找出不同重心
卡不掉