【CF】121 Div.1 C. Fools and Roads

题意是给定一棵树。同时,给定如下k个查询:

给出任意两点u,v,对u到v的路径所经过的边进行加计数。

k个查询后,分别输出各边的计数之和。

思路利用LCA,对cnt[u]++, cnt[v]++,并对cnt[LCA(u, v)] -= 2.
然后dfs求解各边的计数。

 /* 191C */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = 1e5+;
const int maxd = ;
vpii E[maxn];
bool visit[maxn];
int ans[maxn];
int cnt[maxn];
int deep[maxn];
int pre[maxn][maxd]; void dfs(int u, int fa) {
int sz = SZ(E[u]), v; deep[u] = deep[fa] + ;
rep(i, , sz) {
v = E[u][i].fir;
if (v == fa)
continue;
pre[v][] = u;
rep(j, , maxd)
pre[v][j] = pre[pre[v][j-]][j-];
dfs(v, u);
}
} int LCA(int u, int v) {
if (deep[u] > deep[v])
swap(u, v);
if (deep[u] < deep[v]) {
int tmp = deep[v] - deep[u];
rep(i, , maxd) {
if (tmp & (<<i))
v = pre[v][i];
}
} if (u != v) {
per(i, , maxd) {
if (pre[u][i] != pre[v][i]) {
u = pre[u][i];
v = pre[v][i];
}
}
return pre[u][];
} else {
return u;
}
} int dfs2(int u, int eid) {
int ret = , sz = SZ(E[u]);
int e, v; visit[u] = true;
rep(i, , sz) {
v = E[u][i].fir;
e = E[u][i].sec;
if (!visit[v]) {
ret += dfs2(v, e);
}
}
ret += cnt[u];
ans[eid] = ret; return ret;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n;
int u, v, fa; scanf("%d", &n);
rep(i, , n) {
scanf("%d %d", &u, &v);
E[u].pb(mp(v, i));
E[v].pb(mp(u, i));
} dfs(, ); int k; scanf("%d", &k);
while (k--) {
scanf("%d %d", &u, &v);
fa = LCA(u, v);
++cnt[u];
++cnt[v];
cnt[fa] -= ;
} dfs2(, );
rep(i, , n)
printf("%d ", ans[i]);
putchar('\n'); #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
上一篇:CF191C Fools and Roads - 树剖解法


下一篇:LCA+差分【CF191C】Fools and Roads