//finish
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=101000;
int n,m,dp[N][2],dep[N],a[N],b[N],c[N];
VI g[N],qs[N];
#define LOGN 24
int up[N][LOGN];
void dfs(int x,int f) {
up[x][0]=f;
dep[x]=dep[f]+1;
for (auto u:g[x]) if (u!=f) dfs(u,x);
}
int lca(int x,int y) {
if (dep[x]<dep[y]) swap(x,y);
per(i,0,LOGN) if (dep[up[x][i]]>=dep[y]) x=up[x][i];
if (x==y) return x;
per(i,0,LOGN) if (up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
if (x!=y) x=up[x][0];
return x;
}
int lift(int x,int k) {
rep(i,0,LOGN) if (k>>i&1) x=up[x][i];
return x;
}
int dist(int x,int y) {
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void gao(int x,int f) {
for (auto u:g[x]) if (x!=f) gao(u,x),dp[x][0]+=max(dp[u][0],dp[u][1]);
for (auto p:qs[x]) {
if (a[p]==x&&b[p]==x) dp[x][1]=max(dp[x][1],dp[x][0]+c[p]);
else {
if (a[p]==x) {
int pb=lift(b[p],dist(b[p],x)-1);
dp[x][1]=max(dp[x][1],dp[a[p]][0]+dp[b[p]][0]+dp[x][0]-max(dp[pb][0],dp[pb][1])+c[p]);
} else {
if (b[p]==x) {
int pa=lift(a[p],dist(a[p],x)-1);
dp[x][1]=max(dp[x][1],dp[a[p]][0]+dp[b[p]][0]+dp[x][0]-max(dp[pa][0],dp[pa][1])+c[p]);
} else {
int pa=lift(a[p],dist(a[p],x)-1);
int pb=lift(b[p],dist(b[p],x)-1);
dp[x][1]=max(dp[x][1],dp[a[p]][0]+dp[b[p]][0]+dp[x][0]-max(dp[pa][0],dp[pa][1])-max(dp[pb][0],dp[pb][1])+c[p]);
}
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
rep(i,1,n) {
int x,y;
scanf("%d%d",&x,&y);
g[x].pb(y);
g[y].pb(x);
}
dfs(1,0);
rep(j,1,LOGN) rep(i,1,n+1) up[i][j]=up[up[i][j-1]][j-1];
rep(i,1,m+1) {
scanf("%d%d%d",a+i,b+i,c+i);
qs[lca(a[i],b[i])].pb(i);
}
gao(1,0);
printf("%lld",max(dp[1][0],dp[1][1]));
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:84:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
84 | printf("%lld",max(dp[1][0],dp[1][1]));
| ~~~^ ~~~~~~~~~~~~~~~~~~~~~~
| | |
| | int
| long long int
| %d
election_campaign.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d%d",a+i,b+i,c+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
236 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
