树上点分治学习记录 -电脑资料

    跟着机房的潮流学了点分治，发现这个东西其实还蛮好写的，学会思想，很容易YY出来，

树上点分治学习记录

    POJ 1741 TREE

    点分治的模板题，首先设点x到当前子树跟root的距离为gx,则满足gx+gy≤k可以加进答案，但是注意如果x,y在同一棵子树中，就要删去对答案的贡献，以为x,y会在其所在的子树中在计算一次。注意无根树转有根树的过程，需要选取树的重心防止复杂度从O(nlog2n)退化为O(n2)code:

<code class="hljs perl">#include<iostream>#include<cstdio>#include<cstring>#include#define inf 100000using namespace std;struct hp{    int u,v,w;}a[20001];struct hq{    int size;}tree[10001];bool done[10001];int point[10001],next[20001];int len[10001];int n,m,e=0,t=0;int size,root,sizenow,tot,ans=0;void add(int u,int v,int w){    e++; a[e].u=u; a[e].v=v; a[e].w=w; next[e]=point[u]; point[u]=e;    e++; a[e].u=v; a[e].v=u; a[e].w=w; next[e]=point[v]; point[v]=e;}void findsize(int now,int last){    int i,tmp=0;    sizenow++;    for (i=point[now];i;i=next[i])      if (a[i].v!=last&&!done[a[i].v])        findsize(a[i].v,now);}void findroot(int now,int last){    int i,tmp=0;    tree[now].size=1; tmp=0;    for (i=point[now];i;i=next[i])      if (a[i].v!=last&&!done[a[i].v])        {          findroot(a[i].v,now);          tree[now].size+=tree[a[i].v].size;          if (tree[a[i].v].size>tmp)            tmp=tree[a[i].v].size;        }    if (sizenow-tree[now].size>tmp) tmp=sizenow-tree[now].size;    if (tmp<size) if="" int="" road="" root="now;" size="tmp;}" tmp="0;" void="">m) return;    for (i=point[now];i;i=next[i])      if (a[i].v!=last&&!done[a[i].v])        findroad(a[i].v,now,road+a[i].w);}int calc(int k){    int i,l,r,ret=0;    sort(len+1,len+t+1);    for (l=1,r=t;l<r;) ans="0;" ans-="calc(m-2*a[i].w);" code="" e="0;" else="" for="" i="point[root];i;i=next[i])" if="" int="" return="" size="inf;" sizenow="0;" t="0;" void="" while=""></r;)></size)></cstring></cstdio></iostream></code>