P4556 [Vani有约会]雨天的尾巴

akxlaizh · 2021-09-27 15:58:26 · 个人记录

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,mod=998244353;

int h[N],ne[N<<1],e[N<<1],idx;
void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;return ;}
vector<PII>Q[N];
int son[N],siz[N],cnt[N],ans[N],flag;
vector<PII>T[N];
bool dis[N];
int f[N],pre[N];

struct cmp{
    bool operator() (int a,int b){
        return cnt[a]>cnt[b]||(cnt[a]==cnt[b]&&a<b);
    }
};
set<int,cmp>se;
int find(int u){if(u!=f[u])f[u]=find(f[u]);return f[u];}

void dfs(int u,int fa)
{
    siz[u]=1;pre[u]=fa;
    for(int i=h[u];~i;i=ne[i])
    {
        int t=e[i];
        if(t==fa)continue;
        dfs(t,u); 
        if(siz[son[u]]<siz[t])son[u]=t;
        siz[u]+=siz[t];
    }
    dis[u]=1;

    for(auto r:Q[u])
    {
        int x=r.first,y=r.second;
        if(!dis[x])continue;
        int d=find(x);
        T[u].push_back({y,1});T[x].push_back({y,1});
        T[d].push_back({y,-1});
        T[pre[d]].push_back({y,-1});
    }
    f[u]=fa;
    return ;
}

void calc(int u,int fa,int val)
{
    for(auto r:T[u])
    {
        int x=r.first,y=r.second;
        if(se.find(x)!=se.end())se.erase(x);
        cnt[x]+=y*val;
        se.insert(x);
    }

    for(int i=h[u];~i;i=ne[i])
    {
        int t=e[i];
        if(t==fa||t==flag)continue;
        calc(t,u,val); 
    }
}

void dfs(int u,int fa,int keep)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int t=e[i];
        if(t==fa||t==son[u])continue;
        dfs(t,u,0);
    }
    if(son[u])dfs(son[u],u,1),flag=son[u];
    calc(u,fa,1);
    flag=0;
    ans[u]=*se.begin();
    if(!keep)calc(u,fa,-1);
}

int main()
{
    se.insert(0);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)f[i]=i,h[i]=-1;
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b);
        add(h,b,a);
    }

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        Q[a].push_back({b,c});
        if(a!=b)Q[b].push_back({a,c});
    }
    dfs(1,0);
    dfs(1,0,1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}