首页 > 代码库 > HDU4916 Count on the path(树dp??)

HDU4916 Count on the path(树dp??)

2024-07-16 01:44:17   223人阅读

这道题的题意其实有点略晦涩，定义f(a,b)为 minimum of vertices not on the path between vertices a and b. 其实它加一个minimum index of vertices应该会好理解一点吧。看了一下题解，还有程序，才理清思路。

首先比较直接的是如果两点的路径没有经过根节点1的话，那么答案就直接是1，否则的话就必然有从根节点出发的两条路径，题解里说的预处理出f[u]表示不在根节点到u的路径上的点的最小值，然后取f[u]和f[v]的最小值看了我半天。因为如果是这样的话，那么下面这个图不就可以轻易cha掉这种做法？

1->2  1->3  2->4  4->6  4->7  3->5  5->8  5->9

询问(6,8)的时候显然f(6)是3，f(8)是2，那么输出的答案就会是2，但实际上应该输出的是7。

后来仔细探究了才发现，f[u]存的只是  从不在根节点到u的路径的最小值（其中不包括根节点到别的子节点的路径），换言之上面的f[6]里只存了7，f[8]里只存了9，所以min(7,9)=7。

但是这个时候我们可能就会出错了，因为如果根节点如果连出去有第三条路径的话，那么这条路径的最小值我们是没有包含到的，所以对于根节点我们要存它最小值的子树，还有也要存对于每个节点它来自于哪个子树。

剩下的就是一个类似树dp的过程了。

然后题目还温馨提示了可能会超时，可能要写个输入挂什么的，所以写邻接表的可能都不能写vector的形式了吧。

#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define maxn 1005000#define inf 0x3f3f3f3fint child[maxn][4];int subtree[maxn];int path[maxn];int fa[maxn];int bel[maxn];int que[maxn];int qh, qt;int n, nQ;int head[maxn];int nxt[maxn<<1];int vv[maxn<<1];int tot;void add_Edge(int u,int v){	vv[tot] = v; nxt[tot] = head[u]; head[u] = tot++;}void bfs(){	qh = qt = 0;	que[qt++] = 1; fa[1] = -1;	while (qh < qt){		int u = que[qh++];		for (int i = head[u]; ~i; i=nxt[i]){			int v = vv[i];			if (v == fa[u]) continue;			fa[v] = u;			que[qt++] = v;		}	}	for (int i = 0; i <= n; ++i){		for (int j = 0; j < 4; ++j){			child[i][j] = inf;		}	}	for (int i = n - 1; i >= 0; --i){		int u = que[i]; subtree[u] = u;		for (int j = head[u]; ~j; j=nxt[j]){			int v = vv[j];			if (v == fa[u]) continue;			child[u][3] = subtree[v];			sort(child[u], child[u] + 4);		}		subtree[u] = min(subtree[u], child[u][0]);	}	qh = qt = 0;	for (int i = head[1]; ~i; i=nxt[i]){		int v = vv[i];		que[qt++] = v;		bel[v] = subtree[v];		path[v] = inf;	}	while (qh < qt){		int u = que[qh++];		for (int i = head[u]; ~i; i=nxt[i]){			int v = vv[i];			if (v == fa[u]) continue;			bel[v] = bel[u];			if (subtree[v] == child[u][0]){				path[v] = min(path[u], child[u][1]);			}			else{				path[v] = min(path[u], child[u][0]);			}			que[qt++] = v;		}		path[u] = min(path[u], child[u][0]);	}}int query(int qu, int qv){	if (qu > qv) swap(qu, qv);	if (qu != 1 && bel[qu] == bel[qv]) return 1;	int i = 0;	while (child[1][i] == bel[qu] || child[1][i] == bel[qv]){		i++;	}	int ret = qu == 1 ? path[qv] : min(path[qu], path[qv]);	ret = min(ret, child[1][i]);	return ret;}inline void scan(int &n){	char cc;	for (; cc = getchar(), cc<‘0‘ || cc>‘9‘;);	n = cc - ‘0‘;	for (; cc = getchar(), cc >= ‘0‘&&cc <= ‘9‘;)		n = n * 10 + cc - ‘0‘;}int main(){	while (cin >> n >> nQ){		tot = 0; memset(head, -1, sizeof(head));		int ui, vi;		for (int i = 0; i < n - 1; ++i){			//scan(ui); scan(vi);			scanf("%d%d", &ui, &vi);			add_Edge(ui, vi);			add_Edge(vi, ui);		}		bfs();		int last = 0;		for (int i = 0; i < nQ; ++i){			//scan(ui); scan(vi);			scanf("%d%d", &ui, &vi);			ui ^= last; vi ^= last;			printf("%d\n", last=query(ui, vi));		}	}	return 0;}

 


联系
我们