|
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
题目描述
小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。
输入描述:
第一行一个整数N代表景区的个数。
接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。
接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。
接下来一行一个整数Q，表示有Q次询问。
接下来的Q行每行两个整数x,y,代表小A的位置在x，而他想要去的地方是y。
输出描述:
对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力
输入
复制
4
1 2
1 3
2 4
3 4
2
1 3
3 4
输出
复制
1
0
题解
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
const int maxn=3e5+5;
const int INF=1e9+5;
int head[maxn<<1];int d[maxn];
int fa[maxn][20];
struct node{
? ? int to,next;
}edge[maxn<<1];
int cnt1=0;
void add_edge(int from,int to)
{
? ? cnt1++;
? ? edge[cnt1].to=to;
? ? edge[cnt1].next=head[from];
? ? head[from]=cnt1;
}
int lca(int a,int b)
{
? ? if(d[a]<d[b]) swap(a,b);
? ? for(int i=19;i>=0;i--)
? ? {
? ? ? ? if(d[fa[a][i]]>=d[b]) a=fa[a][i];
? ? }
? ? if(a==b) return a;
? ? for(int i=19;i>=0;i--)
? ? {
? ? ? ? if(fa[a][i]!=fa[b][i])
? ? ? ? {
? ? ? ? ? ? a=fa[a][i];
? ? ? ? ? ? b=fa[b][i];
? ? ? ? }
? ? }
? ? return fa[a][0];
}
queue<int> qu;
signed main()
{
? ? int n;scanf("%lld",&n);
? ? memset(head,-1,sizeof(head));
? ? memset(fa,-1,sizeof(fa));
? ? for(int i=1;i<=n;i++) d[i]=INF;
? ? for(int i=0;i<n-1;i++)
? ? {
? ? ? ? int from,to;
? ? ? ? scanf("%lld%lld",&from,&to);
? ? ? ? add_edge(from,to);
? ? ? ? add_edge(to,from);
? ? }
? ? int a,b;scanf("%lld%lld",&a,&b);
? ? d[1]=0;qu.push(1);
? ? while(!qu.empty())
? ? {
? ? ? ? int from=qu.front();qu.pop();
? ? ? ? for(int i=head[from];i!=-1;i=edge[i].next)
? ? ? ? {
? ? ? ? ? ? int to=edge[i].to;
? ? ? ? ? ? if(d[to]>d[from]+1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? d[to]=d[from]+1;
? ? ? ? ? ? ? ? fa[to][0]=from;
? ? ? ? ? ? ? ? qu.push(to);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? for(int k=1;k<20;k++)
? ? {
? ? ? ? for(int j=1;j<=n;j++)
? ? ? ? {
? ? ? ? ? ? if(fa[j][k-1]!=-1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? fa[j][k]=fa[fa[j][k-1]][k-1];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? int q;scanf("%lld",&q);
? ? while(q--)
? ? {
? ? ? ? int from,to;scanf("%lld%lld",&from,&to);
? ? ? ? int v=lca(from,to);
? ? ? ? int ans=INF;
? ? ? ? ans=min(ans,d[from]+d[to]-2*d[v]);
? ? ? ? int b1=lca(from,b);int a1=lca(a,to);
? ? ? ? ans=min(ans,d[from]+d[b]-2*d[b1]+d[to]+d[a]-2*d[a1]);
? ? ? ? a1=lca(from,a),b1=lca(b,to);
? ? ? ? ans=min(ans,d[from]+d[a]-2*d[a1]+d[to]+d[b]-2*d[b1]);
? ? ? ? printf("%lld\n",ans);
? ? }
}
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
题目描述
已知有?nnn 个节点，有?n?1n-1n?1 条边，形成一个树的结构。
给定一个根节点 kkk，每个节点都有一个权值，节点i的权值为 viv_ivi?。
给?mmm 个操作，操作有两种类型：
1 a x ：表示将节点?aaa 的权值加上?xxx
2 a ：表示求?aaa 节点的子树上所有节点的和（包括?aaa 节点本身）
输入描述:
第一行给出三个正整数 n,m,kn,m,kn,m,k，表示树的节点数、操作次数、和这棵树的根节点.
第二行给出?nnn 个正整数，第?iii 个正整数表示第 iii?个节点的权值?valival_ivali?
下面 n?1n-1n?1?行每行两个正整数 u,vu,vu,v，表示边的两个端点
接下来?mmm 行，每行给出一个操作
输出描述:
对于每个类型为 2 的操作,输出一行一个正整数,表示以?aaa 为根的子树的所有节点的权值和
示例1
输入
复制5 6 1 1 2 3 4 5 1 3 1 2 2 4 2 5 1 2 10 1 3 10 1 4 5 1 5 1 2 3 2 2
5 6 1
1 2 3 4 5
1 3
1 2
2 4
2 5
1 2 10
1 3 10
1 4 5
1 5 1
2 3
2 2
输出
复制13 27
13
27
链接：https://ac.nowcoder.com/acm/contest/27836/C
来源：牛客网
?
题目描述
已知有?nnn 个节点，有?n?1n-1n?1 条边，形成一个树的结构。
给定一个根节点 kkk，每个节点都有一个权值，节点i的权值为 viv_ivi?。
给?mmm 个操作，操作有两种类型：
1 a x ：表示将节点?aaa 的权值加上?xxx
2 a ：表示求?aaa 节点的子树上所有节点的和（包括?aaa 节点本身）
输入描述:
第一行给出三个正整数 n,m,kn,m,kn,m,k，表示树的节点数、操作次数、和这棵树的根节点.
第二行给出?nnn 个正整数，第?iii 个正整数表示第 iii?个节点的权值?valival_ivali?
下面 n?1n-1n?1?行每行两个正整数 u,vu,vu,v，表示边的两个端点
接下来?mmm 行，每行给出一个操作
输出描述:
对于每个类型为 2 的操作,输出一行一个正整数,表示以?aaa 为根的子树的所有节点的权值和
示例1
输入
复制5 6 1 1 2 3 4 5 1 3 1 2 2 4 2 5 1 2 10 1 3 10 1 4 5 1 5 1 2 3 2 2
5 6 1
1 2 3 4 5
1 3
1 2
2 4
2 5
1 2 10
1 3 10
1 4 5
1 5 1
2 3
2 2
输出
复制13 27
13
27
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n;
int past[maxn],now[maxn],val[maxn],top[maxn],depth[maxn],fa[maxn],son[maxn],s[maxn],head[maxn<<1],ctv[maxn];
struct node1{
? ? int to,next;
}edge[maxn<<1];
int cc;
void add_edge(int from,int to)
{
? ? cc++;
? ? edge[cc].to=to;
? ? edge[cc].next=head[from];
? ? head[from]=cc;
}
struct node{
? ? int sum;
}tree[maxn*4];
void Pushup(int rt)
{
? ? tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void build(int rt,int l,int r)
{
? ? if(l==r){
? ? ? ? tree[rt].sum=val[past[l]];
? ? ? ? return ;
? ? }
? ? int m=(l+r)/2;
? ? build(rt<<1,l,m);
? ? build(rt<<1|1,m+1,r);
? ? Pushup(rt);
}
void change(int rt,int l,int r,int pos,int c)
{
? ? if(l==r){
? ? ? ? tree[rt].sum+=c;
? ? ? ? return ;
? ? }
? ? int m=(l+r)/2;
? ? if(pos<=m) change(rt<<1,l,m,pos,c);
? ? if(pos>m) change(rt<<1|1,m+1,r,pos,c);
? ? Pushup(rt);
}
int query(int rt,int l,int r,int L,int R)
{
? ? int ans=0;
? ? if(l>=L&&r<=R)
? ? {
? ? ? ? return tree[rt].sum;
? ? }
? ? int m=(l+r)/2;
? ? if(L<=m) ans+=query(rt<<1,l,m,L,R);
? ? if(R>m) ans+=query(rt<<1|1,m+1,r,L,R);
? ? return ans;
}
void init()
{
? ? memset(head,-1,sizeof(head));
}
void dfs1(int root)
{
? ? depth[root]=depth[fa[root]]+1;
? ? s[root]=1;
? ? for(int i=head[root];i!=-1;i=edge[i].next)
? ? {
? ? ? ? int to=edge[i].to;
? ? ? ? if(to!=fa[root])
? ? ? ? {
? ? ? ? ? ? fa[to]=root;
? ? ? ? ? ? dfs1(to);
? ? ? ? ? ? s[root]+=s[to];
? ? ? ? ? ? if(s[son[root]]<s[to])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? son[root]=to;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int id=0;
void dfs2(int root,int f)
{
? ? top[root]=f;
? ? now[root]=++id;
? ? past[id]=root;
? ? if(son[root]) dfs2(son[root],f);
? ? for(int i=head[root];i!=-1;i=edge[i].next)
? ? {
? ? ? ? int to=edge[i].to;
? ? ? ? if(to!=fa[root]&&to!=son[root])
? ? ? ? {
? ? ? ? ? ? dfs2(to,to);
? ? ? ? }
? ? }
? ? ctv[root]=id;
}
signed main()
{
? ? int m;int k;
? ? scanf("%lld%lld%lld",&n,&m,&k);
? ? init();
? ? for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
? ? for(int i=0;i<n-1;i++)
? ? {
? ? ? ? int from,to; scanf("%lld%lld",&from,&to);
? ? ? ? add_edge(from,to);
? ? ? ? add_edge(to,from);
? ? }
? ? dfs1(k);dfs2(k,k);
? ? build(1,1,n);
? ? while(m--)
? ? {
? ? ? ? int op;scanf("%lld",&op);
? ? ? ? if(op==1)
? ? ? ? {
? ? ? ? ? ? int a,x;scanf("%lld%lld",&a,&x);
? ? ? ? ? ? change(1,1,n,now[a],x);
? ? ? ? }
? ? ? ? if(op==2)
? ? ? ? {
? ? ? ? ? ? int ?a;scanf("%lld",&a);
? ? ? ? ? ?printf("%lld\n",query(1,1,n,now[a],ctv[a]));
? ? ? ? }
? ? }
}
|