LCT 求条(玄2关
查看原帖
LCT 求条(玄2关
749665
huta0楼主2024/2/26 16:53
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#define int long long
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define drep(a,b,c) for(int a=b;a>=c;a--)
#define a_all a.begin(),a.end()
using namespace std;
typedef long long ll;
const int N = 100010;
int n,m,dep[N],a,b,c,a1,a2;
bool vis[N]={0};
struct edge {
      int v,w;
};
vector<edge> e[N];
void dfs(int u,int fa) {
      for(auto ed:e[u]) {
            int v=ed.v,w=ed.w;
            if(v==fa) continue;
            dep[v]=dep[u]+w;
            dfs(v,u);
      }
}
namespace hikari {
     struct node {
           int p,v=0,sum,tag,add=0,tp=0,nw=0;
           int s[2];
     } tr[2*N];
     #define fa(x) tr[x].p
     #define lc(x) tr[x].s[0]
     #define rc(x) tr[x].s[1]
     #define ntrt(x) lc(fa(x))==x||rc(fa(x))==x
     void pk(int x) {
     	  tr[x].v+=tr[x].nw;
          tr[x].sum+=tr[x].tp;
          tr[x].add=1;
	 }
     void pushup(int x) {
           tr[x].sum=tr[lc(x)].sum+tr[x].v+tr[rc(x)].sum;
           tr[x].tp=tr[lc(x)].tp+tr[x].nw+tr[rc(x)].tp;
     }
     void pushdown(int x) {
           if(tr[x].add) {
                 pk(lc(x));
				 pk(rc(x));
                 tr[x].add=0;
           }
           if(tr[x].tag) {
                 swap(lc(x),rc(x));
                 tr[lc(x)].tag^=1;
                 tr[rc(x)].tag^=1;
                 tr[x].tag=0;
           }
     }
     void pushall(int x) {
           if(ntrt(x)) pushall(fa(x));
           pushdown(x);
     }
     void rotate(int x) {
           int y=fa(x),z=fa(y);
           int k= rc(y)==x;
           if(ntrt(y))
                tr[z].s[rc(z)==y]=x;
           fa(x)=z;
           tr[y].s[k]=tr[x].s[k^1];
           fa(tr[x].s[k^1])=y;
           tr[x].s[k^1]=y;
           fa(y)=x;
           pushup(y); pushup(x);
     }
     void splay(int x) {
           pushall(x);
           while(ntrt(x)) {
                 int y=fa(x),z=fa(y);
                 if(ntrt(y)) 
                      rotate((rc(y)==x^rc(z)==y)?x:y);
                 rotate(x);
           }
     }
     void access(int x) {
           int y=0;
           while(x) {
                 splay(x);
                 rc(x)=y;
                 pushup(x);
                 y=x; x=fa(x);
           }
     }
     void mkrt(int x) {
           access(x);
           splay(x);
           tr[x].tag^=1;
     }
     inline int fdrt(int x) {
            access(x);
            splay(x);
            while(lc(x)) pushdown(x),x=lc(x);
            splay(x);
            return x;
     }
     void split(int x,int y) {
            mkrt(x);
            access(y);
            splay(y);
     }
     void link(int x,int y) {
            mkrt(x);
            if(fdrt(y)!=x) fa(x)=y;
     }
     void cut(int x,int y) {
            mkrt(x);
            if(fdrt(y)==x&&fa(y)==x&&!lc(y))
                 rc(x)=fa(y)=0;
     }
};
using namespace hikari;
signed main() {
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    rep(i,1,n-1) {
          cin>>a>>b>>c;
          e[a].push_back({b,c});
          e[b].push_back({a,c});
          tr[i+n].nw=c; tr[i+n].v=0;
          link(a,i+n); link(i+n,b);
    }
    dep[1]=0;
    dfs(1,1);
    a1+=dep[1]; split(1,1); a2+=tr[1].sum;
    rep(i,1,m) {
          cin>>a;
          a1+=dep[a];
          split(1,a);
          a2+=tr[a].sum;
          pk(a);
          cout<<(2*i*a1-4*a2)<<endl;
    }
    //rep(i,1,n) cout<<dep[i]<<" ";
    return 0;
}
2024/2/26 16:53
加载中...