列表

详情

NC237552. Squirrels

描述

Two squirrels live on a tree with n nodes. The nodes are connected by n-1 edges, the i-th of which connects node a_i and node b_i. It is guaranteed that any node is reachable from any other node.

A big snow currently hit the tree. The i-th edge of the tree is now covered with c_i units of snow.

For each of the following m days, the squirrels decide to have a meeting. On the i-th day, the first squirrel will start on node x_i, and the second squirrel will start on node y_i. As they are smart squirrels, they will walk along the shortest path between the two nodes. They need to clear away the snow on the edges all along the way. However, clearing away snow is really hard work, and on the i-th day both of the squirrels can only clear away at most k_i units of snow. Each squirrel will walk along the chosen path, and continuously clear away the snow until it reaches its destination, or its upper limit of snow-clearing amount has been reached.

The i-th meeting is considered if after the clearing process, there is no snow on the shortest path between x_i and y_i. The squirrels want you to tell them whether each meeting is successful or not. Please note that each clearing process has an impact on all the meetings held in the following days.

输入描述

The first line of input contains a single integer , denoting the number of nodes of the tree.

Each of the following n-1 lines contains three integers , denoting an edge on the tree. It is guaranteed that the given edges form a tree.

The next line contains a single integer , denoting the number of meetings.

Each of the next m lines contains three integers , denoting the parameters of the i-th meeting.

输出描述

Output m lines, the i-th of which contains a string  or , respectively representing the i-th meeting is successful or not.

示例1

输入: 

3
1 2 2
1 3 3
3
2 3 1
2 3 1
2 3 1

输出: 

NO
NO
YES

示例2

输入: 

8
2 1 7
3 2 8
4 2 3
5 2 9
6 4 9
7 4 9
8 4 3
5
5 1 6
6 3 6
1 6 7
4 1 5
2 3 0

输出: 

NO
NO
YES
YES
NO

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 2972ms, 内存消耗: 115952K, 提交时间: 2022-10-14 12:41:49 

#include<iostream>
using namespace std;
#define maxn 800010
int fa[maxn][22], dis[maxn], dsu[maxn], dep[maxn];
struct edge
{
    int v, val, nxt;
}e[2*maxn];
int hd[maxn], cnt;
void addedge(int u, int v, int val)
{
    e[++cnt].v = v;
    e[cnt].val = val;
    e[cnt].nxt = hd[u];
    hd[u] = cnt;
}
int get_dsu(int x)
{
    if(dsu[x] == x) return x;
    return dsu[x] = get_dsu(dsu[x]);
}
void dfs(int now, int fr)
{
    fa[now][0] = fr;
    dep[now] = dep[fr] + 1;
    if(now == 1 || dis[now] != 0) dsu[now] = now;
    else dsu[now] = fr;
    for(int i = hd[now]; i; i = e[i].nxt)
    {
        if(e[i].v != fr)
        {
            dis[e[i].v] = e[i].val;
            dfs(e[i].v, now);
        }
    }
}
int n, m;
void get_fa()
{
    for(int i = 1; i <= 20; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            fa[j][i] = fa[fa[j][i-1]][i-1];
        }
    }
}
int get_lca(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    int tmp = dep[x] - dep[y];
    for(int i = 20; i >= 0; i--)
    {
        if(tmp >= (1 << i))
        {
            x = fa[x][i];
            tmp -= (1 << i);
        }
    }
    if(x == y) return x;
    for(int i = 20; i >= 0; i--)
    {
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
int main()
{
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
    ios::sync_with_stdio(false);
    cin >> n;
    int a, b, c, x, y, c1, c2;
    for(int i = 1; i < n; i++)
    {
        cin >> a >> b >> c;
        addedge(a, b, c);
        addedge(b, a, c);
    }
    dfs(1, 0);
    get_fa();
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        x = get_dsu(a);
        y = get_dsu(b);
        int lca = get_lca(a, b);
        c1 = c2 = c;
        while(c1 != 0 && dep[x] > dep[lca])
        {
            if(c1 >= dis[x])
            {
                c1 -= dis[x];
                dis[x] = 0;
                dsu[x] = fa[x][0];
                x = get_dsu(x);
            }
            else
            {
                dis[x] -= c1;
                c1 = 0;
            }
        }
        while(c2 != 0 && dep[y] > dep[lca])
        {
            if(c2 >= dis[y])
            {
                c2 -= dis[y];
                dis[y] = 0;
                dsu[y] = fa[y][0];
                y = get_dsu(y);
            }
            else
            {
                dis[y] -= c2;
                c2 = 0;
            }
        }
        if(dep[x] > dep[lca] && c2 != 0)
        {
            while(dep[x] > dep[lca] && c2 != 0)
            {
                int tmp = x;
                for(int j = 20; j >= 0; j--)
                {
                    if(dep[fa[tmp][j]] < dep[lca]) continue;
                    if(get_dsu(lca) != get_dsu(fa[tmp][j])) tmp = fa[tmp][j];
                }
                if(c2 >= dis[tmp])
                {
                    c2 -= dis[tmp];
                    dis[tmp] = 0;
                    dsu[tmp] = fa[tmp][0];
                    x = get_dsu(x);
                }
                else
                {
                    dis[tmp] -= c2;
                    c2 = 0;
                }
            }
        }
        else if(dep[y] > dep[lca] && c1 != 0)
        {
            while(dep[y] > dep[lca] && c1 != 0)
            {
                int tmp = y;
                for(int j = 20; j >= 0; j--)
                {
                    if(dep[fa[tmp][j]] < dep[lca]) continue;
                    if(get_dsu(lca) != get_dsu(fa[tmp][j])) tmp = fa[tmp][j];
                }
                if(c1 >= dis[tmp])
                {
                    c1 -= dis[tmp];
                    dis[tmp] = 0;
                    dsu[tmp] = fa[tmp][0];
                    y = get_dsu(y);
                }
                else
                {
                    dis[tmp] -= c1;
                    c1 = 0;
                }
            }
        }
        if(dep[x] <= dep[lca] && dep[y] <= dep[lca]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

C++ 解法, 执行用时: 1256ms, 内存消耗: 141332K, 提交时间: 2022-05-28 17:57:08 

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=a,i##_end=b;i<i##_end;++i)
using ll=long long;
#ifdef flukehn
void debug_out(){cerr<<endl;}
template<typename Head,typename ...Tail>
void debug_out(Head H,Tail ...T){
  cerr<<" "<<H;
  debug_out(T...);
}
#define dbg(...) cerr<<"L"<<__LINE__<<":["<<#__VA_ARGS__<<"]",debug_out(__VA_ARGS__)
#define debug(...) cerr<<__VA_ARGS__
#else
#define dbg(...) 0
#define debug(...) 0
#endif
using pa=pair<int,int>;
const int N=800111;
vector<pa> e[N];
int g[N];
int dep[N];
int fa[N][22];
void dfs(int x){
  for(int i=1;fa[x][i-1];++i)
    fa[x][i]=fa[fa[x][i-1]][i-1];
  for(auto [y,w]:e[x]){
    if(y==fa[x][0])continue;
    fa[y][0]=x;
    dep[y]=dep[x]+1;
    g[y]=w;
    dfs(y);
  }
}
int f[N];
int n;
int find(int x){
  return f[x]==x?x:f[x]=find(f[x]);
}

int isanc(int x,int y){
  if(x==y) return 1;
  if(dep[x]<=dep[y])return 0;
  int s=dep[x]-dep[y];
  for(int i=20;i>=0;--i)
    if(s>>i&1) x=fa[x][i];
  return x==y;
}
int gao(int x,int y,int k){
  int k1=k,k2=k;
  x=find(x),y=find(y);
  while(x!=y){
    if(dep[x]<dep[y])swap(x,y),swap(k1,k2);
    if(x>1&&k1) {
      if(k1>=g[x]) k1-=g[x],g[x]=0,x=f[x]=find(fa[x][0]);
      else g[x]-=k1,k1=0;
    }else if(y== 1 || !k2 || isanc(x,y)){
      break;
    }else{
      if(k2>=g[y]) k2-=g[y],g[y]=0,y=f[y]=find(fa[y][0]);
      else g[y]-=k2,k2=0;
    }
  }
  if(x==y) return 1;
  if(dep[x]<dep[y])swap(x,y),swap(k1,k2);
  if(!isanc(x,y)) return 0;
  while(k2 && x!=y) {
    int z=x;
    for(int i=19;i>=0;--i)
      if(dep[find(fa[z][i])]>dep[y]) z=fa[z][i];
    if(k2>=g[z]){
      k2-=g[z];
      g[z]=0;
      f[z]=find(fa[z][0]);
    }else{
      g[z]-=k2;
      k2=0;
    }
    x=find(x);
  }
  return x==y;
}
int main(){
#ifdef flukehn
  freopen("H.in","r",stdin);
#endif
  ios::sync_with_stdio(0),cin.tie(0);
  cin>>n;
  for(int i=1;i<n;++i){
    int a,b,c;
    cin>>a>>b>>c;
    e[a].emplace_back(b,c);
    e[b].emplace_back(a,c);
  }
  for(int i=1;i<=n;++i) f[i]=i;
  dfs(1);
  int Q;
  cin>>Q;
  while(Q--){
    int x,y,k;
    cin>>x>>y>>k;
    int r=gao(x,y,k);
    if(r)cout<<"YES\n";
    else cout<<"NO\n";
    //cout.flush();
  }
}

上一题

© 2025 nowcoder.com