[省选前题目整理][POJ1741]Tree(点分治)

题目链接

http://poj.org/problem?id&＃61;1741

题目大意

求树上使得a到b的最短路小于等于K的无序点对(a,b)个数

思路

经典点分治问题。

如上图&＃xff0c;所有符合题意的路径只可能是上面两种形态之一。我们就是要求出所有这样的长度小于等于K的路径&＃xff0c;并去掉不合法的路径(重复经过了某条边的路径以及重复计算的路径&＃xff0c;实际上点分治是不会出现重复计算的情况的&＃xff0c;因为将一个树以重心分割成若干子树后&＃xff0c;下一层分治要找的路径分别在各个子树中&＃xff0c;不会出现重复)

首先对于当前分治的树&＃xff0c;找出它的重心&＃xff0c;将重心当成当前分治的树的根节点&＃xff08;注意此时要用一个vis数组标记重心为true&＃xff0c;这样在DFS求DFS序、求树的重心等操作时不访问标记过的点&＃xff0c;就能保证每次DFS时不会越出当前分治的树的范围&＃xff01;&＃xff09;

然后对这个新的树&＃xff0c;从重心(根节点)开始进行DFS&＃xff0c;构造出一个DFS序列&＃xff0c;并得到每个点的深度&＃xff0c;对这个DFS序按照每个点的深度进行升序排序

现在我们要快速地找出所有的点对(a,b),a,b是当前子树中的非根节点&＃xff0c;并且depth[a]&＃43;depth[b]<&＃61;K

然后维护两个指针L,R&＃xff0c;初始时分别指向排序后的DFS序的两端&＃xff0c;表示L和所有的i属于[L&＃43;1,R]&＃xff0c;并且(L,i)是符合我们要找的点对的条件的。那么若depth[L]&＃43;depth[R]<&＃61;K&＃xff0c;则所有的(L,i),i属于[L&＃43;1,R]显然都是符合depth[L]&＃43;depth[i]<&＃61;K这一条件的&＃xff0c;符合上述条件的点对个数就&＃43;&＃61;R−L,L加1.否则说明R过大&＃xff0c;R减1

但是这样做会出现一些不合法情况&＃xff0c;如下图&＃xff0c;以重心为根节点的子树中&＃xff0c;可能出现有两个节点的LCA并不是重心&＃xff0c;而是重心下的某个点&＃xff0c;这样的点对之间的路径不是最短路

去掉这样的不合法情况的方法也比较简单&＃xff0c;即在分治到重心下的某个儿子的子树前&＃xff0c;先设这个儿子深度为重心到该儿子的边权&＃xff0c;然后以该儿子为根节点DFS这个子树&＃xff0c;求出DFS序并排序&＃xff0c;和之前做法基本上是一样的&＃xff0c;设最终在这个子树中找到的所有满足条件的点对个数为x，和之前做法相反，这次是在总答案中减去x&＃xff0c;因为这些点对都是如上图形态一样的不合法的点对。

代码

#include
#include
#include
#include
#include
#include #define MAXN 10100using namespace std;int n,K,ans&＃61;0;struct edge
{int u,v,w,next;
}edges[MAXN*2];int head[MAXN],nCount&＃61;0;void AddEdge(int U,int V,int W)
{edges[&＃43;&＃43;nCount].u&＃61;U;edges[nCount].v&＃61;V;edges[nCount].w&＃61;W;edges[nCount].next&＃61;head[U];head[U]&＃61;nCount;
}vector<int>seq; //dfs序列
int size[MAXN],vis[MAXN],f[MAXN],root&＃61;0; //root&＃61;重心,size[i]&＃61;子树i大小,f[i]&＃61;以i为分治的树的根的话&＃xff0c;点i下面最大的儿子子树大小
int sizeOfTree; //当前分治的树的大小
int depth[MAXN];void getroot(int u,int fa)
{size[u]&＃61;1;f[u]&＃61;0;for(int p&＃61;head[u];p!&＃61;-1;p&＃61;edges[p].next){int v&＃61;edges[p].v;if(v&＃61;&＃61;fa||vis[v]) continue; //!!!!getroot(v,u);size[u]&＃43;&＃61;size[v];f[u]&＃61;max(f[u],size[v]);}f[u]&＃61;max(f[u],sizeOfTree-size[u]);if(f[u]}void getdepth(int u,int fa)
{seq.push_back(depth[u]);size[u]&＃61;1;for(int p&＃61;head[u];p!&＃61;-1;p&＃61;edges[p].next){int v&＃61;edges[p].v;if(v&＃61;&＃61;fa||vis[v]) continue;depth[v]&＃61;depth[u]&＃43;edges[p].w;getdepth(v,u);size[u]&＃43;&＃61;size[v];}
}int cal(int u,int w) //连接到u的边边权为w,
{seq.clear();depth[u]&＃61;w;getdepth(u,0);sort(seq.begin(),seq.end());int sum&＃61;0;for(int l&＃61;0,r&＃61;seq.size()-1;lif(seq[l]&＃43;seq[r]<&＃61;K){sum&＃43;&＃61;r-l;l&＃43;&＃43;;}else r--;}return sum;
}void work(int u)
{ans&＃43;&＃61;cal(u,0);vis[u]&＃61;true;for(int p&＃61;head[u];p!&＃61;-1;p&＃61;edges[p].next){int v&＃61;edges[p].v;if(!vis[v]){ans-&＃61;cal(v,edges[p].w); //删去不合法的路径f[0]&＃61;sizeOfTree&＃61;size[v];root&＃61;0; //重置树的重心getroot(v,0);work(root);}}
}int main()
{while(scanf("%d%d",&n,&K)!&＃61;EOF&&!(!n&&!K)){memset(head,-1,sizeof(head));nCount&＃61;0;root&＃61;0;ans&＃61;0;memset(vis,false,sizeof(vis));for(int i&＃61;1;iint u,v,w;scanf("%d%d%d",&u,&v,&w);AddEdge(u,v,w);AddEdge(v,u,w);}f[0]&＃61;sizeOfTree&＃61;n; //!!!!!getroot(1,0);work(root);printf("%d\n",ans);}return 0;
}