3653: 谈笑风生
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 628 Solved: 245
[Submit][Status][Discuss]
Description
设T 为一棵有根树，我们做如下的定义：
• 设a和b为T 中的两个不同节点。如果a是b的祖先，那么称“a比b不知道高明到哪里去了”。
• 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数x，那么称“a 与b 谈笑风生”。
给定一棵n个节点的有根树T，节点的编号为1 到 n，根节点为1号节点。你需要回答q 个询问，询问给定两个整数p和k，问有多少个有序三元组(a;b;c)满足：
1. a、b和 c为 T 中三个不同的点，且 a为p 号节点；
2. a和b 都比 c不知道高明到哪里去了；
3. a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。
Input
输入文件的第一行含有两个正整数n和q，分别代表有根树的点数与询问的个数。接下来n - 1行，每行描述一条树上的边。每行含有两个整数u和v，代表在节点u和v之间有一条边。
接下来q行，每行描述一个操作。第i行含有两个整数，分别表示第i个询问的p和k。
Output
输出 q 行，每行对应一个询问，代表询问的答案。
Sample Input
5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
Sample Output
3
1
3
1
3
HINT
1<=P<=N
1<=K<=N
N<=300000
Q<=300000
Source
Solution
答案显然是$(size[x]-1)*min(deep[x],K)+\sum_{dis(x,y)<=K,y\epsilon x}^{y}(size[y]-1)$
考虑求后面那些东西，可以利用可持久化线段树来做
用deep作为下标，维护size。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 300010
#define LL long long
int N,Q;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int deep[MAXN],size[MAXN],pl[MAXN],pr[MAXN],pre[MAXN],dfn,maxd;
void DFS(int now,int last)
{
pl[now]=++dfn; pre[dfn]=now; size[now]=;
maxd=max(maxd,deep[now]);
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
deep[edge[i].to]=deep[now]+;
DFS(edge[i].to,now);
size[now]+=size[edge[i].to];
}
pr[now]=dfn;
}
struct SegmentTreeNode{int ls,rs; LL sum;}tree[MAXN*];
int root[MAXN],sz;
void Update(int &now,int last,int l,int r,int pos,int val)
{
now=++sz;
tree[now].sum=tree[last].sum+val;
if (l==r) return;
int mid=(l+r)>>;
tree[now].ls=tree[last].ls,tree[now].rs=tree[last].rs;
if (pos<=mid) Update(tree[now].ls,tree[last].ls,l,mid,pos,val);
else Update(tree[now].rs,tree[last].rs,mid+,r,pos,val);
}
LL Query(int now,int l,int r,int L,int R)
{
if (!now) return 0LL;
if (L==l && R==r) return tree[now].sum;
int mid=(l+r)>>;
if (R<=mid) return Query(tree[now].ls,l,mid,L,R);
else if (L>mid) return Query(tree[now].rs,mid+,r,L,R);
else return Query(tree[now].ls,l,mid,L,mid)+Query(tree[now].rs,mid+,r,mid+,R);
}
int main()
{
N=read(),Q=read();
for (int x,y,i=; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
DFS(,);
// for (int i=1; i<=N; i++)
// printf("%d [%d , %d] %d %d\n",pre[i],pl[pre[i]],pr[pre[i]],size[pre[i]],deep[pre[i]]);
for (int i=; i<=N; i++) Update(root[i],root[i-],,maxd,deep[pre[i]],size[pre[i]]-);
for (int i=; i<=Q; i++)
{
int p=read(),K=read();
LL ans=0LL;
ans=(LL)(size[p]-)*min(deep[p],K)+Query(root[pr[p]],,maxd,deep[p]+,deep[p]+K)-Query(root[pl[p]-],,maxd,deep[p]+,deep[p]+K);
printf("%lld\n",ans);
}
return ;
}
被Char哥-拍死了